{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Reachable Nodes With Restrictions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #graph #array #hash-table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #图 #数组 #哈希表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: reachableNodes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #受限条件下可到达节点的数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>现有一棵由 <code>n</code> 个节点组成的无向树，节点编号从 <code>0</code> 到 <code>n - 1</code> ，共有 <code>n - 1</code> 条边。</p>\n",
    "\n",
    "<p>给你一个二维整数数组 <code>edges</code> ，长度为 <code>n - 1</code> ，其中 <code>edges[i] = [a<sub>i</sub>, b<sub>i</sub>]</code> 表示树中节点 <code>a<sub>i</sub></code> 和 <code>b<sub>i</sub></code> 之间存在一条边。另给你一个整数数组 <code>restricted</code> 表示 <strong>受限</strong> 节点。</p>\n",
    "\n",
    "<p>在不访问受限节点的前提下，返回你可以从节点<em> </em><code>0</code><em> </em>到达的 <strong>最多</strong> 节点数目<em>。</em></p>\n",
    "\n",
    "<p>注意，节点 <code>0</code> <strong>不</strong> 会标记为受限节点。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/06/15/ex1drawio.png\" style=\"width: 402px; height: 322px;\">\n",
    "<pre><strong>输入：</strong>n = 7, edges = [[0,1],[1,2],[3,1],[4,0],[0,5],[5,6]], restricted = [4,5]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>上图所示正是这棵树。\n",
    "在不访问受限节点的前提下，只有节点 [0,1,2,3] 可以从节点 0 到达。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/06/15/ex2drawio.png\" style=\"width: 412px; height: 312px;\">\n",
    "<pre><strong>输入：</strong>n = 7, edges = [[0,1],[0,2],[0,5],[0,4],[3,2],[6,5]], restricted = [4,2,1]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>上图所示正是这棵树。\n",
    "在不访问受限节点的前提下，只有节点 [0,5,6] 可以从节点 0 到达。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>edges.length == n - 1</code></li>\n",
    "\t<li><code>edges[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= a<sub>i</sub>, b<sub>i</sub> &lt; n</code></li>\n",
    "\t<li><code>a<sub>i</sub> != b<sub>i</sub></code></li>\n",
    "\t<li><code>edges</code> 表示一棵有效的树</li>\n",
    "\t<li><code>1 &lt;= restricted.length &lt; n</code></li>\n",
    "\t<li><code>1 &lt;= restricted[i] &lt; n</code></li>\n",
    "\t<li><code>restricted</code> 中的所有值 <strong>互不相同</strong></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [reachable-nodes-with-restrictions](https://leetcode.cn/problems/reachable-nodes-with-restrictions/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [reachable-nodes-with-restrictions](https://leetcode.cn/problems/reachable-nodes-with-restrictions/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['7\\n[[0,1],[1,2],[3,1],[4,0],[0,5],[5,6]]\\n[4,5]', '7\\n[[0,1],[0,2],[0,5],[0,4],[3,2],[6,5]]\\n[4,2,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for a,b, w in edges:\n",
    "            g[a].append((b,w))\n",
    "            g[b].append((a,w))\n",
    "        dist = [float('inf')] * n \n",
    "        def dijk(s, dist):\n",
    "            dist[s] = 0\n",
    "            vis = [0] * n \n",
    "            Q = [(dist[s], s)]\n",
    "            while Q:\n",
    "                d, u = heapq.heappop(Q)\n",
    "                if vis[u]:\n",
    "                    continue \n",
    "                vis[u] = 1\n",
    "                if d > maxMoves:\n",
    "                    continue\n",
    "                for v, w in g[u]:\n",
    "                    if dist[v] > dist[u] + w + 1:\n",
    "                        dist[v] = dist[u] + w + 1\n",
    "                        heapq.heappush(Q,(dist[v], v))\n",
    "        dijk(0, dist) \n",
    "        ans = 0\n",
    "        for a, b, w in edges:\n",
    "            da = max(maxMoves - dist[a], 0)\n",
    "            db = max(maxMoves - dist[b], 0)\n",
    "            ans += min(da + db, w) \n",
    "        for i in range(n):\n",
    "            if dist[i] <= maxMoves:\n",
    "                ans += 1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        d = [1000000000 for _ in range(n)]\n",
    "        d[0] = 0\n",
    "        maps = {_:[] for _ in range(n)}\n",
    "        for edge in edges:\n",
    "            maps[edge[0]].append((edge[1],edge[2]))\n",
    "            maps[edge[1]].append((edge[0],edge[2]))\n",
    "        q = [(0,0)]\n",
    "        ans = 1\n",
    "        while q:\n",
    "            now = heapq.heappop(q)\n",
    "            for y in maps[now[1]]:\n",
    "                temp = now[0] + y[1]\n",
    "                if temp <= maxMoves:\n",
    "                    if temp < d[y[0]]:\n",
    "                        d[y[0]] = temp + 1\n",
    "                        heapq.heappush(q,(d[y[0]],y[0]))\n",
    "        ans = sum(c <= maxMoves for c in d)\n",
    "        for x, y, cnt in edges:\n",
    "            a = max(maxMoves - d[x], 0)\n",
    "            b = max(maxMoves - d[y], 0)\n",
    "            ans += min(a + b, cnt)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for a,b, w in edges:\n",
    "            g[a].append((b,w))\n",
    "            g[b].append((a,w))\n",
    "        dist = [float('inf')] * n \n",
    "        def dijk(s, dist):\n",
    "            dist[s] = 0\n",
    "            vis = [0] * n \n",
    "            Q = [(dist[s], s)]\n",
    "            while Q:\n",
    "                d, u = heapq.heappop(Q)\n",
    "                if vis[u]:\n",
    "                    continue \n",
    "                vis[u] = 1\n",
    "                for v, w in g[u]:\n",
    "                    if dist[v] > dist[u] + w + 1:\n",
    "                        dist[v] = dist[u] + w + 1\n",
    "                        heapq.heappush(Q,(dist[v], v))\n",
    "        dijk(0, dist) \n",
    "        ans = 0\n",
    "        for a, b, w in edges:\n",
    "            da = max(maxMoves - dist[a], 0)\n",
    "            db = max(maxMoves - dist[b], 0)\n",
    "            ans += min(da + db, w) \n",
    "        for i in range(n):\n",
    "            if dist[i] <= maxMoves:\n",
    "                ans += 1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        d = [1000000000 for _ in range(n)]\n",
    "        d[0] = 0\n",
    "        maps = {_:[] for _ in range(n)}\n",
    "        for edge in edges:\n",
    "            maps[edge[0]].append((edge[1],edge[2]))\n",
    "            maps[edge[1]].append((edge[0],edge[2]))\n",
    "        q = [(0,0)]\n",
    "        ans = 1\n",
    "        while q:\n",
    "            now = heapq.heappop(q)\n",
    "            for y in maps[now[1]]:\n",
    "                temp = now[0] + y[1]\n",
    "                if temp < d[y[0]]:\n",
    "                    d[y[0]] = temp + 1\n",
    "                    heapq.heappush(q,(d[y[0]],y[0]))\n",
    "        ans = sum(c <= maxMoves for c in d)\n",
    "        for x, y, cnt in edges:\n",
    "            a = max(maxMoves - d[x], 0)\n",
    "            b = max(maxMoves - d[y], 0)\n",
    "            ans += min(a + b, cnt)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v, cnt in edges:\n",
    "            g[u].append((v, cnt + 1))\n",
    "            g[v].append((u, cnt + 1))\n",
    "\n",
    "        dist = self.dijkstra(g, 0)\n",
    "        ans = sum(d <= maxMoves for d in dist) # 这里首先统计出来不是边上的节点的个数\n",
    "        # 太妙了\n",
    "        for u, v, cnt in edges:\n",
    "            # 这里计算u和v之间的节点的个数，排除了u和v本身，我们考虑任何一条边，maxMoves -dist[u] 和0取最大值，如果\n",
    "            # dist[u] > maxMoves则不用计算，为0\n",
    "            # dist[u] < maxMoves则意味着有maxMoves - dist[u]的节点都会被计算进去，但是如果maxMoves远远大于dist[u]呢？关键我们最后取了和cnt对比的最小值\n",
    "            # 可以确保只计算uv之间的节点数\n",
    "            a = max(maxMoves - dist[u], 0)\n",
    "            b = max(maxMoves - dist[v], 0)\n",
    "            ans += min(a + b, cnt)\n",
    "        return ans\n",
    "        \n",
    "    def dijkstra(self,g: List[List[Tuple[int]]], start: int) -> List[int]:\n",
    "        dist = [inf] * len(g)\n",
    "        dist[start] = 0\n",
    "        h = [(0, start)]\n",
    "        #print(f'g:{g}')\n",
    "        while h:\n",
    "            d, x = heappop(h)\n",
    "            # 什么情况下会出现d > dist[x],考虑在这种情况，一个节点是有可能重复进入h队列的，\n",
    "            # 比如一开始的时候被最近的节点更新了距离，然后另一个最近的节点通过另一个路径又更新了同一个点，就有可能出现同一个节点但是距离不同的情况再队列里，这个时候d > dist[x]其实是可以放弃的\n",
    "            # print(f'dist:{dist},d:{d},x:{x},h:{h}')\n",
    "            # if d > dist[x]:\n",
    "            #     continue\n",
    "            for y, wt in g[x]:\n",
    "                new_d = dist[x] + wt\n",
    "                if new_d < dist[y]:\n",
    "                    dist[y] = new_d\n",
    "                    heappush(h, (new_d, y))\n",
    "        return dist\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        # 无向图，邻接表 edges[i,j,k]， k表示将边(i,j)分出的新的节点数\n",
    "        # 计算从节点0出发，可到达多少个新节点：最大移动距离： maxMoves\n",
    "        g = [[] for _ in range(n)] # 建图， 边权为cnt+1\n",
    "        for u, v, cnt in edges:\n",
    "            g[u].append((v, cnt + 1))\n",
    "            g[v].append((u, cnt + 1))\n",
    "        dist = self.dijkstra(g, 0) # dist存放从0出发到各个节点的最短路\n",
    "        ans = sum(d <= maxMoves for d in dist) # 可以在maxMoves不内到达的点的个数\n",
    "        for u, v, cnt in edges: # 每条边上的新节点\n",
    "            a = max(maxMoves - dist[u], 0)\n",
    "            b = max(maxMoves - dist[v], 0)\n",
    "            ans += min(a + b, cnt)\n",
    "        return ans \n",
    "    #Dijkstra 算法模板\n",
    "\n",
    "    def dijkstra(self, g, start) -> List[int]:\n",
    "        dist = [inf] * len(g)\n",
    "        dist[start] = 0\n",
    "        h = [(0, start)]\n",
    "        while h:\n",
    "            d, x = heappop(h)\n",
    "            if d > dist[x]: continue\n",
    "            for y, wt in g[x]:\n",
    "                new_d = dist[x] + wt \n",
    "                if new_d < dist[y]: \n",
    "                    dist[y] = new_d\n",
    "                    heappush(h, (new_d, y))\n",
    "        return dist "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v, cnt in edges:\n",
    "            g[u].append((v, cnt + 1))\n",
    "            g[v].append((u, cnt + 1))  # 建图\n",
    "\n",
    "        dist = self.dijkstra(g, 0)  # 从 0 出发的最短路\n",
    "\n",
    "        ans = sum(d <= maxMoves for d in dist)  # 可以在 maxMoves 步内到达的点的个数\n",
    "        for u, v, cnt in edges:\n",
    "            a = max(maxMoves - dist[u], 0)\n",
    "            b = max(maxMoves - dist[v], 0)\n",
    "            ans += min(a + b, cnt)  # 这条边上可以到达的节点数\n",
    "        return ans\n",
    "\n",
    "    # Dijkstra 算法模板\n",
    "    # 返回从 start 到每个点的最短路\n",
    "    def dijkstra(self, graph: List[List[Tuple[int]]], start: int) -> List[int]:\n",
    "        import heapq\n",
    "\n",
    "        dist = [float('inf')] * len(graph)\n",
    "        dist[start] = 0\n",
    "        que = []\n",
    "        # 建最小堆\n",
    "        heapq.heappush(que, (0, start))\n",
    "        while len(que) > 0:\n",
    "            cost, node = heapq.heappop(que)\n",
    "            if dist[node] < cost:\n",
    "                continue\n",
    "            for new_node, weight in graph[node]:\n",
    "                next_cost = cost + weight\n",
    "                if dist[new_node] > next_cost:\n",
    "                    dist[new_node] = next_cost\n",
    "                    heapq.heappush(que, (next_cost, new_node))\n",
    "        return dist\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        # 无向图，邻接表 edges[i,j,k]， k表示将边(i,j)分出的新的节点数\n",
    "        # 计算从节点0出发，可到达多少个新节点：最大移动距离： maxMoves\n",
    "        g = [[] for _ in range(n)] # 建图， 边权为cnt+1\n",
    "        for u, v, cnt in edges:\n",
    "            g[u].append((v, cnt + 1))\n",
    "            g[v].append((u, cnt + 1))\n",
    "        dist = self.dijkstra(g, 0) # dist存放从0出发到各个节点的最短路\n",
    "        ans = sum(d <= maxMoves for d in dist) # 可以在maxMoves不内到达的点的个数\n",
    "        for u, v, cnt in edges: # 每条边上的新节点\n",
    "            a = max(maxMoves - dist[u], 0)\n",
    "            b = max(maxMoves - dist[v], 0)\n",
    "            ans += min(a + b, cnt)\n",
    "        return ans\n",
    "        \n",
    "    # Dijkstra 算法模板\n",
    "    def dijkstra(self, g, start) -> List[int]:\n",
    "        dist = [inf] * len(g)\n",
    "        dist[start] = 0\n",
    "        h = [(0, start)]\n",
    "        while h: \n",
    "            d, x = heappop(h) # 小顶堆，存(d, i)从start到节点i的最短距离是d\n",
    "            # d, x = h.popleft()\n",
    "            # if d > dist[x]: continue # 避免重复访问\n",
    "            for y, wt in g[x]: # 遍历新的节点\n",
    "                new_d = dist[x] + wt # 最短路更新\n",
    "                if new_d < dist[y]: \n",
    "                    dist[y] = new_d # 判断是否更新\n",
    "                    heappush(h, (new_d, y)) # 更新后入堆\n",
    "            \n",
    "        return dist "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v, cnt in edges:\n",
    "            g[u].append((v, cnt + 1))\n",
    "            g[v].append((u, cnt + 1))  # 建图\n",
    "\n",
    "        dist = self.dijkstra(g, 0)  # 从 0 出发的最短路\n",
    "\n",
    "        ans = sum(d <= maxMoves for d in dist)  # 可以在 maxMoves 步内到达的点的个数\n",
    "        for u, v, cnt in edges:\n",
    "            a = max(maxMoves - dist[u], 0)\n",
    "            b = max(maxMoves - dist[v], 0)\n",
    "            ans += min(a + b, cnt)  # 这条边上可以到达的节点数\n",
    "        return ans\n",
    "\n",
    "    # Dijkstra 算法模板\n",
    "    # 返回从 start 到每个点的最短路\n",
    "    def dijkstra(self, g: List[List[Tuple[int]]], start: int) -> List[int]:\n",
    "        dist = [inf] * len(g)\n",
    "        dist[start] = 0\n",
    "        h = [(0, start)]\n",
    "        while h:\n",
    "            d, x = heappop(h)\n",
    "            if d > dist[x]:\n",
    "                continue\n",
    "            for y, wt in g[x]:\n",
    "                new_d = dist[x] + wt\n",
    "                if new_d < dist[y]:\n",
    "                    dist[y] = new_d\n",
    "                    heappush(h, (new_d, y))\n",
    "        return dist\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v, cnt in edges:\n",
    "            g[u].append((v, cnt + 1))\n",
    "            g[v].append((u, cnt + 1))\n",
    "\n",
    "        dist = self.dijkstra(g, 0)\n",
    "        ans = sum(d <= maxMoves for d in dist)\n",
    "        for u, v, cnt in edges:\n",
    "            a = max(maxMoves - dist[u], 0)\n",
    "            b = max(maxMoves - dist[v], 0)\n",
    "            ans += min(a + b, cnt)\n",
    "        return ans\n",
    "        \n",
    "    def dijkstra(self,g: List[List[Tuple[int]]], start: int) -> List[int]:\n",
    "        dist = [inf] * len(g)\n",
    "        dist[start] = 0\n",
    "        h = [(0, start)]\n",
    "        while h:\n",
    "            d, x = heappop(h)\n",
    "            # 什么情况下会出现d > dist[x]\n",
    "            if d > dist[x]:\n",
    "                continue\n",
    "            for y, wt in g[x]:\n",
    "                new_d = dist[x] + wt\n",
    "                if new_d < dist[y]:\n",
    "                    dist[y] = new_d\n",
    "                    heappush(h, (new_d, y))\n",
    "        return dist\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for u, v, cnt in edges:\n",
    "            graph[u].append((v, cnt+1))\n",
    "            graph[v].append((u, cnt+1))\n",
    "\n",
    "        # dijsktra\n",
    "        distances = [float(\"inf\")] * n\n",
    "        distances[0] = 0\n",
    "        hq = [(0, 0)]\n",
    "        while hq:\n",
    "            distance, x = heapq.heappop(hq)\n",
    "            if distance > distances[x]:\n",
    "                continue\n",
    "            for y, weight in graph[x]:\n",
    "                new_distance = distances[x] + weight\n",
    "                if new_distance < distances[y]:\n",
    "                    distances[y] = new_distance\n",
    "                    heapq.heappush(hq, (new_distance, y))\n",
    "\n",
    "        res = sum(distance <= maxMoves for distance in distances)\n",
    "        for u, v, cnt in edges:\n",
    "            a = max(maxMoves - distances[u], 0)\n",
    "            b = max(maxMoves - distances[v], 0)\n",
    "            res += min(a + b, cnt)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v, cnt in edges:\n",
    "            g[u].append((v, cnt + 1))\n",
    "            g[v].append((u, cnt + 1))  # 建图\n",
    "\n",
    "        dist = self.dijkstra(g, 0)  # 从 0 出发的最短路\n",
    "\n",
    "        ans = sum(d <= maxMoves for d in dist)  # 可以在 maxMoves 步内到达的点的个数\n",
    "        for u, v, cnt in edges:\n",
    "            a = max(maxMoves - dist[u], 0)\n",
    "            b = max(maxMoves - dist[v], 0)\n",
    "            ans += min(a + b, cnt)  # 这条边上可以到达的节点数\n",
    "        return ans\n",
    "\n",
    "    # Dijkstra 算法模板\n",
    "    # 返回从 start 到每个点的最短路\n",
    "    def dijkstra(self, g: List[List[Tuple[int]]], start: int) -> List[int]:\n",
    "        dist = [inf] * len(g)\n",
    "        dist[start] = 0\n",
    "        h = [(0, start)]\n",
    "        while h:\n",
    "            d, x = heappop(h)\n",
    "            if d > dist[x]:\n",
    "                continue\n",
    "            for y, wt in g[x]:\n",
    "                new_d = dist[x] + wt\n",
    "                if new_d < dist[y]:\n",
    "                    dist[y] = new_d\n",
    "                    heappush(h, (new_d, y))\n",
    "        return dist\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v, cnt in edges:\n",
    "            g[u].append((v, cnt + 1))\n",
    "            g[v].append((u, cnt + 1))\n",
    "\n",
    "        dist = self.dijkstra(g, 0)\n",
    "        ans = sum(d <= maxMoves for d in dist) # 这里首先统计出来不是边上的节点的个数\n",
    "        # 太妙了\n",
    "        for u, v, cnt in edges:\n",
    "            # 这里计算u和v之间的节点的个数，排除了u和v本身，我们考虑任何一条边，maxMoves -dist[u] 和0取最大值，如果\n",
    "            # dist[u] > maxMoves则不用计算，为0\n",
    "            # dist[u] < maxMoves则意味着有maxMoves - dist[u]的节点都会被计算进去，但是如果maxMoves远远大于dist[u]呢？关键我们最后取了和cnt对比的最小值\n",
    "            # 可以确保只计算uv之间的节点数\n",
    "            a = max(maxMoves - dist[u], 0)\n",
    "            b = max(maxMoves - dist[v], 0)\n",
    "            ans += min(a + b, cnt)\n",
    "        return ans\n",
    "        \n",
    "    def dijkstra(self,g: List[List[Tuple[int]]], start: int) -> List[int]:\n",
    "        dist = [inf] * len(g)\n",
    "        dist[start] = 0\n",
    "        h = [(0, start)]\n",
    "        #print(f'g:{g}')\n",
    "        while h:\n",
    "            d, x = heappop(h)\n",
    "            # 什么情况下会出现d > dist[x],考虑在这种情况，一个节点是有可能重复进入h队列的，\n",
    "            # 比如一开始的时候被最近的节点更新了距离，然后另一个最近的节点通过另一个路径又更新了同一个点，就有可能出现同一个节点但是距离不同的情况再队列里，这个时候d > dist[x]其实是可以放弃的，快速失败\n",
    "            # print(f'dist:{dist},d:{d},x:{x},h:{h}')\n",
    "            # 这里是一个剪枝，快速失败\n",
    "            if d > dist[x]:\n",
    "                continue\n",
    "            for y, wt in g[x]:\n",
    "                new_d = dist[x] + wt\n",
    "                if new_d < dist[y]:\n",
    "                    dist[y] = new_d\n",
    "                    heappush(h, (new_d, y))\n",
    "        return dist\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v, cnt in edges:\n",
    "            g[u].append((v, cnt + 1))\n",
    "            g[v].append((u, cnt + 1))  # 建图\n",
    "\n",
    "        dist = self.dijkstra(g, 0)  # 从 0 出发的最短路\n",
    "\n",
    "        ans = sum(d <= maxMoves for d in dist)  # 可以在 maxMoves 步内到达的点的个数\n",
    "        for u, v, cnt in edges:\n",
    "            a = max(maxMoves - dist[u], 0)\n",
    "            b = max(maxMoves - dist[v], 0)\n",
    "            ans += min(a + b, cnt)  # 这条边上可以到达的节点数\n",
    "        return ans\n",
    "\n",
    "    # Dijkstra 算法模板\n",
    "    # 返回从 start 到每个点的最短路\n",
    "    def dijkstra(self, g: List[List[Tuple[int]]], start: int) -> List[int]:\n",
    "        dist = [inf] * len(g)\n",
    "        dist[start] = 0\n",
    "        h = [(0, start)]\n",
    "        while h:\n",
    "            d, x = heappop(h)\n",
    "            if d > dist[x]:\n",
    "                continue\n",
    "            for y, wt in g[x]:\n",
    "                new_d = dist[x] + wt\n",
    "                if new_d < dist[y]:\n",
    "                    dist[y] = new_d\n",
    "                    heappush(h, (new_d, y))\n",
    "        return dist\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        # 从节点 0 出发 可到达的节点数\n",
    "        g = [[] for _ in range(n)]\n",
    "\n",
    "        for x,y,cnt in edges:\n",
    "            g[x].append((y,cnt+1))\n",
    "            g[y].append((x,cnt+1))\n",
    "        dist = [float('inf')]*n\n",
    "        dist[0] = 0\n",
    "        start = 0\n",
    "        hq = [(0,start)]\n",
    "        while hq:\n",
    "            w1,x = heapq.heappop(hq)\n",
    "            if w1 > dist[x]:\n",
    "                continue\n",
    "            for y,w2 in g[x]:\n",
    "                w = w1 + w2\n",
    "                if w < dist[y]:\n",
    "                    dist[y] = w\n",
    "                    heapq.heappush(hq,(w,y))\n",
    "        ans = 0\n",
    "        sum(d <= maxMoves for d in dist)\n",
    "        for x in range(n):\n",
    "            if dist[x] <= maxMoves:\n",
    "                ans += 1\n",
    "        print(ans)\n",
    "        for x,y,w in edges:\n",
    "            # 如果dist[x]>maxMoves,则为负,取0\n",
    "            a = max(maxMoves - dist[x],0) #如果从x还可以走a步\n",
    "            b = max(maxMoves - dist[y],0) #如果从y出发还可以走步\n",
    "            ans += min(a+b,w)\n",
    "        return ans\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        # 无向图，邻接表 edges[i,j,k]， k表示将边(i,j)分出的新的节点数\n",
    "        # 计算从节点0出发，可到达多少个新节点：最大移动距离： maxMoves\n",
    "        g = [[] for _ in range(n)] # 建图， 边权为cnt+1\n",
    "        for u, v, cnt in edges:\n",
    "            g[u].append((v, cnt + 1))\n",
    "            g[v].append((u, cnt + 1))\n",
    "        dist = self.dijkstra(g, 0) # dist存放从0出发到各个节点的最短路\n",
    "        ans = sum(d <= maxMoves for d in dist) # 可以在maxMoves不内到达的点的个数\n",
    "        for u, v, cnt in edges: # 每条边上的新节点\n",
    "            a = max(maxMoves - dist[u], 0)\n",
    "            b = max(maxMoves - dist[v], 0)\n",
    "            ans += min(a + b, cnt)\n",
    "        return ans \n",
    "    #Dijkstra 算法模板\n",
    "\n",
    "\n",
    "    # 加权有向图，单源最短路， 返回dist[i]从0出发到节点i的最短路权重和\n",
    "    def dijkstra(self, g:List[List[Tuple[int]]], start:int) -> List[int]:\n",
    "        dist = [inf] * len(g)\n",
    "        dist[start] = 0\n",
    "        h = [(0, start)] # 堆代替deque\n",
    "        while h:\n",
    "            d, x = heappop(h) # \n",
    "            if d > dist[x]:\n",
    "                continue\n",
    "            for y, wt in g[x]: # 点x到y的距离：wt\n",
    "                new_d = dist[x] + wt \n",
    "                if new_d < dist[y]: # 新的距离更小，更具路径\n",
    "                    dist[y] = new_d\n",
    "                    heappush(h, (new_d, y))\n",
    "        return dist \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v, cnt in edges:\n",
    "            g[u].append((v, cnt + 1))\n",
    "            g[v].append((u, cnt + 1))\n",
    "        \n",
    "        dis = [inf] * n\n",
    "        dis[0] = 0\n",
    "        h = [(0, 0)]\n",
    "        while h:\n",
    "            d, x = heappop(h)\n",
    "            if dis[x] < d:\n",
    "                continue\n",
    "            for y, wt in g[x]:\n",
    "                if dis[x] + wt < dis[y]:\n",
    "                    dis[y] = dis[x] + wt\n",
    "                    heappush(h, (dis[y], y))\n",
    "        ans = sum(maxMoves >= d for d in dis)\n",
    "        for x, y, cnt in edges:\n",
    "            a = max(maxMoves - dis[x], 0)\n",
    "            b = max(maxMoves - dis[y], 0)\n",
    "            ans += min(a + b, cnt)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        graph = collections.defaultdict(list)\n",
    "        for a, b, c in edges:\n",
    "            graph[a].append([b, c + 1])\n",
    "            graph[b].append([a, c + 1])\n",
    "        dis = [float('inf')] * n \n",
    "        dis[0] = 0\n",
    "        queue = collections.deque([0])\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            for nei, cost in graph[cur]:\n",
    "                if dis[nei] > dis[cur] + cost:\n",
    "                    dis[nei] = dis[cur] + cost \n",
    "                    queue.append(nei)\n",
    "        res = 0\n",
    "        for a, b, c in edges:\n",
    "            res += min(c, max(maxMoves - dis[a], 0) + max(maxMoves - dis[b], 0))\n",
    "        for node in range(n):\n",
    "            if dis[node] <= maxMoves:\n",
    "                res += 1 \n",
    "        return res \n",
    "\n",
    "\n",
    "     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v, cnt in edges:\n",
    "            g[u].append((v, cnt + 1))\n",
    "            g[v].append((u, cnt + 1))  # 建图\n",
    "\n",
    "        dist = self.dijkstra(g, 0)  # 从 0 出发的最短路\n",
    "\n",
    "        ans = sum(d <= maxMoves for d in dist)  # 可以在 maxMoves 步内到达的点的个数\n",
    "        for u, v, cnt in edges:\n",
    "            a = max(maxMoves - dist[u], 0)\n",
    "            b = max(maxMoves - dist[v], 0)\n",
    "            ans += min(a + b, cnt)  # 这条边上可以到达的节点数\n",
    "        return ans\n",
    "\n",
    "    # Dijkstra 算法模板\n",
    "    # 返回从 start 到每个点的最短路\n",
    "    def dijkstra(self, g: List[List[Tuple[int]]], start: int) -> List[int]:\n",
    "        dist = [inf] * len(g)\n",
    "        dist[start] = 0\n",
    "        h = [(0, start)]\n",
    "        while h:\n",
    "            d, x = heappop(h)\n",
    "            if d > dist[x]:\n",
    "                continue\n",
    "            for y, wt in g[x]:\n",
    "                new_d = dist[x] + wt\n",
    "                if new_d < dist[y]:\n",
    "                    dist[y] = new_d\n",
    "                    heappush(h, (new_d, y))\n",
    "        return dist\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v, cnt in edges:\n",
    "            g[u].append((v, cnt + 1))\n",
    "            g[v].append((u, cnt + 1))  # 建图\n",
    "\n",
    "        dist = self.dijkstra(g, 0)  # 从 0 出发的最短路\n",
    "\n",
    "        ans = sum(d <= maxMoves for d in dist)  # 可以在 maxMoves 步内到达的点的个数\n",
    "        for u, v, cnt in edges:\n",
    "            a = max(maxMoves - dist[u], 0)\n",
    "            b = max(maxMoves - dist[v], 0)\n",
    "            ans += min(a + b, cnt)  # 这条边上可以到达的节点数\n",
    "        return ans\n",
    "\n",
    "    # Dijkstra 算法模板\n",
    "    # 返回从 start 到每个点的最短路\n",
    "    def dijkstra(self, g: List[List[Tuple[int]]], start: int) -> List[int]:\n",
    "        dist = [inf] * len(g)\n",
    "        dist[start] = 0\n",
    "        h = [(0, start)]\n",
    "        while h:\n",
    "            d, x = heappop(h)\n",
    "            if d > dist[x]:\n",
    "                continue\n",
    "            for y, wt in g[x]:\n",
    "                new_d = dist[x] + wt\n",
    "                if new_d < dist[y]:\n",
    "                    dist[y] = new_d\n",
    "                    heappush(h, (new_d, y))\n",
    "        return dist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        # 从节点 0 出发 可到达的节点数\n",
    "        g = [[] for _ in range(n)]\n",
    "\n",
    "        for x,y,cnt in edges:\n",
    "            g[x].append((y,cnt+1))\n",
    "            g[y].append((x,cnt+1))\n",
    "        dist = [float('inf')]*n\n",
    "        dist[0] = 0\n",
    "        start = 0\n",
    "        hq = [(0,start)]\n",
    "        while hq:\n",
    "            w1,x = heapq.heappop(hq)\n",
    "            if w1 > dist[x]:\n",
    "                continue\n",
    "            for y,w2 in g[x]:\n",
    "                w = w1 + w2\n",
    "                if w < dist[y]:\n",
    "                    dist[y] = w\n",
    "                    heapq.heappush(hq,(w,y))\n",
    "        ans = 0\n",
    "        # sum(d <= maxMoves for d in dist)\n",
    "        for x in range(n):# 可以在 maxMoves 步内到达的点的个数\n",
    "            if dist[x] <= maxMoves:\n",
    "                ans += 1\n",
    "        print(ans)\n",
    "        for x,y,w in edges:\n",
    "            # 如果dist[x]>maxMoves,则为负,取0\n",
    "            a = max(maxMoves - dist[x],0) #如果从x还可以走a步\n",
    "            b = max(maxMoves - dist[y],0) #如果从y出发还可以走步\n",
    "            ans += min(a+b,w)# 这条边上可以到达的节点数\n",
    "        return ans\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "原来的边可以新增节点？\n",
    "细分后。。。替换成cnt+1条边，共cnt+2个节点\n",
    "乍一看，需要维护到达每个新节点的最短距离\n",
    "\n",
    "是一个非常复杂的图\n",
    "朴素的bfs跑不动\n",
    "所以，最好不要考虑新增的节点，一旦考虑连建图都见不出来了\n",
    "修改边权跑dij，跑完后遍历每条边，计算这些边上有多少可达节点\n",
    "稠密图，用n^2算法\n",
    "\n",
    "'''\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        g=[[]*n for _ in range(n)]\n",
    "        for x,y,w in edges:\n",
    "            g[x].append((y,w+1))\n",
    "            g[y].append((x,w+1))\n",
    "        dis=[inf]*n\n",
    "        vis=[False]*n\n",
    "        dis[0]=0\n",
    "        #不能用bfs了，悲\n",
    "        while True:\n",
    "            mn=inf\n",
    "            for i in range(n):\n",
    "                if dis[i]<mn and not vis[i]:\n",
    "                    mn=dis[i]\n",
    "                    x=i\n",
    "            if mn==inf:\n",
    "                break\n",
    "            #将与x相邻的边松弛\n",
    "            vis[x]=True\n",
    "            for y,w in g[x]:\n",
    "                if dis[y]>dis[x]+w:\n",
    "                    dis[y]=dis[x]+w\n",
    "        ans=0\n",
    "        for x in dis:\n",
    "            if x<=maxMoves:\n",
    "                ans+=1\n",
    "        #如何避免重复计算？\n",
    "        for x,y,w in edges:\n",
    "            dx,dy=dis[x],dis[y]\n",
    "            #下标从1开始一直到w\n",
    "            farx=min(maxMoves-dx,w) if dx<maxMoves else 0\n",
    "            fary=min(maxMoves-dy,w) if dy<maxMoves else 0\n",
    "            ans+=min(farx+fary,w)\n",
    "        return ans\n",
    "            \n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "原来的边可以新增节点？\n",
    "细分后。。。替换成cnt+1条边，共cnt+2个节点\n",
    "乍一看，需要维护到达每个新节点的最短距离\n",
    "\n",
    "是一个非常复杂的图\n",
    "朴素的bfs跑不动\n",
    "所以，最好不要考虑新增的节点，一旦考虑连建图都见不出来了\n",
    "修改边权跑dij，跑完后遍历每条边，计算这些边上有多少可达节点\n",
    "稠密图，用n^2算法\n",
    "\n",
    "'''\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        g=[[]*n for _ in range(n)]\n",
    "        for x,y,w in edges:\n",
    "            g[x].append((y,w+1))\n",
    "            g[y].append((x,w+1))\n",
    "        dis=[inf]*n\n",
    "        vis=[False]*n\n",
    "        dis[0]=0\n",
    "        #不能用bfs了，悲\n",
    "        while True:\n",
    "            mn=inf\n",
    "            for i in range(n):\n",
    "                if dis[i]<mn and not vis[i]:\n",
    "                    mn=dis[i]\n",
    "                    x=i\n",
    "            if mn==inf:\n",
    "                break\n",
    "            #将与x相邻的边松弛\n",
    "            vis[x]=True\n",
    "            for y,w in g[x]:\n",
    "                if dis[y]>dis[x]+w:\n",
    "                    dis[y]=dis[x]+w\n",
    "        ans=0\n",
    "        for x in dis:\n",
    "            if x<=maxMoves:\n",
    "                ans+=1\n",
    "        #如何避免重复计算？\n",
    "        for x,y,w in edges:\n",
    "            dx,dy=dis[x],dis[y]\n",
    "            #下标从1开始一直到w\n",
    "            farx=min(maxMoves-dx,w) if dx<maxMoves else 0\n",
    "            fary=min(maxMoves-dy,w) if dy<maxMoves else 0\n",
    "            if farx>=w+1-fary:\n",
    "                ans-=farx+fary-w\n",
    "            ans+=farx+fary\n",
    "        return ans\n",
    "            \n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v, cnt in edges:\n",
    "            g[u].append((v, cnt + 1))\n",
    "            g[v].append((u, cnt + 1))  # 建图\n",
    "\n",
    "        dist = self.dijkstra(g, 0)  # 从 0 出发的最短路\n",
    "\n",
    "        ans = sum(d <= maxMoves for d in dist)  # 可以在 maxMoves 步内到达的点的个数\n",
    "        for u, v, cnt in edges:\n",
    "            a = max(maxMoves - dist[u], 0)\n",
    "            b = max(maxMoves - dist[v], 0)\n",
    "            ans += min(a + b, cnt)  # 这条边上可以到达的节点数\n",
    "        return ans\n",
    "\n",
    "    # Dijkstra 算法模板\n",
    "    # 返回从 start 到每个点的最短路\n",
    "    def dijkstra(self, g: List[List[Tuple[int]]], start: int) -> List[int]:\n",
    "        dist = [inf] * len(g)\n",
    "        dist[start] = 0\n",
    "        h = [(0, start)]\n",
    "        while h:\n",
    "            d, x = heappop(h)\n",
    "            if d > dist[x]:\n",
    "                continue\n",
    "            for y, wt in g[x]:\n",
    "                new_d = dist[x] + wt\n",
    "                if new_d < dist[y]:\n",
    "                    dist[y] = new_d\n",
    "                    heappush(h, (new_d, y))\n",
    "        return dist\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y, w in edges:\n",
    "            g[x].append((y, w + 1))\n",
    "            g[y].append((x, w + 1))\n",
    "\n",
    "        dis = [0] + [inf] * (n - 1)\n",
    "        q = [(0, 0)]\n",
    "        while q:\n",
    "            d, x = heappop(q)\n",
    "            if d > dis[x] : continue\n",
    "            for y, w in g[x]:\n",
    "                nd = dis[x] + w\n",
    "                if nd < dis[y]:\n",
    "                    dis[y] = nd \n",
    "                    heappush(q, (nd, y))\n",
    "\n",
    "        print(dis)\n",
    "        ans = sum(d <= maxMoves for d in dis)\n",
    "\n",
    "        for x, y, w in edges:\n",
    "            a = max(maxMoves - dis[x], 0)\n",
    "            b = max(maxMoves - dis[y], 0)\n",
    "            ans += min(a + b, w)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        graph = defaultdict(list)\n",
    "        for u,v,cnt in edges:\n",
    "            graph[u].append((v,1+cnt))\n",
    "            graph[v].append((u,1+cnt))\n",
    "        \n",
    "        queue = [(0,0)]\n",
    "        dist = [float('inf')]*n\n",
    "        dist[0] = 0\n",
    "        while queue:\n",
    "            dis,x = heapq.heappop(queue)\n",
    "            if dist[x]<dis:\n",
    "                continue\n",
    "            for nextN,nextD in graph[x]:\n",
    "                if dis+nextD < dist[nextN]:\n",
    "                    dist[nextN] = dis + nextD\n",
    "                    heapq.heappush(queue, (dist[nextN],nextN))\n",
    "            pass\n",
    "        \n",
    "        total = 0\n",
    "        for i in range(n):\n",
    "            if dist[i]<=maxMoves:\n",
    "                total += 1\n",
    "        for u,v,cnt in edges:\n",
    "            if dist[u]>maxMoves and dist[v]>maxMoves:\n",
    "                pass\n",
    "            elif dist[u]>maxMoves:\n",
    "                total += (maxMoves - dist[v])\n",
    "            elif dist[v]>maxMoves:\n",
    "                total += (maxMoves - dist[u])\n",
    "            else:\n",
    "                total += min(cnt, maxMoves*2-dist[u]-dist[v])\n",
    "                # if abs(dist[u]-dist[v])==1+cnt:\n",
    "                #     total += cnt\n",
    "                # else:\n",
    "                #     total += min(cnt, maxMoves*2-dist[u]-dist[v])\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        graph = defaultdict(list)\n",
    "        for u, v, nodes in edges:\n",
    "            graph[u].append((v, nodes+1))\n",
    "            graph[v].append((u, nodes+1))\n",
    "        \n",
    "        dist = [inf]*n\n",
    "        dist[0] = 0\n",
    "        q = [(0, 0)]\n",
    "        while q:\n",
    "            dst, u = q.pop(0)\n",
    "            if dst > dist[u]:\n",
    "                continue\n",
    "            for v, distance in graph[u]:\n",
    "                if dist[u]+distance < dist[v]:\n",
    "                    dist[v] = dist[u]+distance\n",
    "                    q.append((dist[v], v))\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if dist[i] <=maxMoves:\n",
    "                ans += 1\n",
    "        for u, v, edge in edges:\n",
    "            t1 = max(0, maxMoves-dist[u])\n",
    "            t2 = max(0, maxMoves-dist[v])\n",
    "            ans += min(edge, t1+t2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        graph = defaultdict(list)\n",
    "        for u,v,cnt in edges:\n",
    "            graph[u].append((v,1+cnt))\n",
    "            graph[v].append((u,1+cnt))\n",
    "        \n",
    "        queue = [(0,0)]\n",
    "        dist = [float('inf')]*n\n",
    "        dist[0] = 0\n",
    "        while queue:\n",
    "            dis,x = heapq.heappop(queue)\n",
    "            if dist[x]<dis:\n",
    "                continue\n",
    "            for nextN,nextD in graph[x]:\n",
    "                if dis+nextD < dist[nextN]:\n",
    "                    dist[nextN] = dis + nextD\n",
    "                    heapq.heappush(queue, (dist[nextN],nextN))\n",
    "            pass\n",
    "        \n",
    "        total = 0\n",
    "        for i in range(n):\n",
    "            if dist[i]<=maxMoves:\n",
    "                total += 1\n",
    "        for u,v,cnt in edges:\n",
    "            if dist[u]>maxMoves and dist[v]>maxMoves:\n",
    "                pass\n",
    "            elif dist[u]>maxMoves:\n",
    "                total += (maxMoves - dist[v])\n",
    "            elif dist[v]>maxMoves:\n",
    "                total += (maxMoves - dist[u])\n",
    "            else:\n",
    "                total += min(cnt, maxMoves*2-dist[u]-dist[v])\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        g = defaultdict(dict)\n",
    "        for a, b, cnt in edges:\n",
    "            g[a][b] = g[b][a] = cnt + 1\n",
    "        # 0到其他点的距离\n",
    "        dist = [0] + [float('inf')] * (n - 1)\n",
    "        h = [(0, 0)]\n",
    "        while h:\n",
    "            a_cnt, a = heappop(h)\n",
    "            if a_cnt > maxMoves:\n",
    "                break\n",
    "            for b, b_cnt in g[a].items():\n",
    "                if a_cnt + b_cnt < dist[b]:\n",
    "                    heappush(h, (a_cnt + b_cnt, b))\n",
    "                    dist[b] = a_cnt + b_cnt\n",
    "            # print(a, dist)\n",
    "        ans = sum(1 for c in dist if c <= maxMoves)\n",
    "        # print(dist)\n",
    "        # 考虑可达的细分结点\n",
    "        for a, b, cnt in edges:\n",
    "            cnt_a = max(0, maxMoves - dist[a])\n",
    "            cnt_b = max(0, maxMoves - dist[b])\n",
    "            cnt = min(cnt, cnt_a + cnt_b)\n",
    "            ans += cnt\n",
    "            # print(a, b, cnt_a, cnt_b, cnt)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for u, v, cnt in edges:\n",
    "            g[u].append((v, cnt + 1))\n",
    "            g[v].append((u, cnt + 1))\n",
    "        q = [(0, 0)]\n",
    "        dist = [0] + [inf] * n\n",
    "        while q:\n",
    "            d, u = heappop(q)\n",
    "            for v, cnt in g[u]:\n",
    "                if (t := d + cnt) < dist[v]:\n",
    "                    dist[v] = t\n",
    "                    q.append((t, v))\n",
    "        ans = sum(d <= maxMoves for d in dist)\n",
    "        for u, v, cnt in edges:\n",
    "            a = min(cnt, max(0, maxMoves - dist[u]))\n",
    "            b = min(cnt, max(0, maxMoves - dist[v]))\n",
    "            ans += min(cnt, a + b)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "import math\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def build_graph(self, edges: List[List[int]]) -> defaultdict:\n",
    "        graph = collections.defaultdict(list)\n",
    "        for u, v, w in edges:\n",
    "            graph[u].append([v, w + 1])\n",
    "            graph[v].append([u, w + 1])\n",
    "        return graph\n",
    "\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        graph = self.build_graph(edges)\n",
    "\n",
    "        dist = [math.inf] * n\n",
    "        heap = [(0, 0)]\n",
    "        count = 0\n",
    "        while heap:\n",
    "            (cost, u) = heapq.heappop(heap)\n",
    "            if cost > maxMoves:\n",
    "                break\n",
    "            if not math.isinf(dist[u]):\n",
    "                continue\n",
    "            dist[u] = cost\n",
    "            count += 1\n",
    "            for v, w in graph[u]:\n",
    "                if not math.isinf(dist[v]):\n",
    "                    continue\n",
    "                heapq.heappush(heap, (cost+w, v))\n",
    "        for u, v, w in edges:\n",
    "            count += min(max(maxMoves - dist[u], 0) + max(maxMoves - dist[v], 0), w)\n",
    "\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x,y,w in edges:\n",
    "            g[x].append((y, w+1))\n",
    "            g[y].append((x, w+1))\n",
    "\n",
    "        dis = self.dijkstra(g, 0)\n",
    "\n",
    "        res = 0\n",
    "        for d in dis:\n",
    "            if d<=maxMoves:\n",
    "                res += 1\n",
    "        \n",
    "        for u, v, w in edges:\n",
    "            a = max(maxMoves-dis[u], 0) \n",
    "            b = max(maxMoves-dis[v], 0)\n",
    "            res += min(a+b, w)\n",
    "        return res\n",
    "    # Dijkstra算法模版\n",
    "    # 返回从stat到每个点的最短路\n",
    "    def dijkstra(self, g, stat):\n",
    "        dis = [inf]*len(g)\n",
    "        dis[stat] = 0\n",
    "        h = [(0, stat)]\n",
    "        while h:\n",
    "            d, x = heappop(h)\n",
    "            if d>dis[x]:\n",
    "                continue\n",
    "            for y, w in g[x]:\n",
    "                new_d = dis[x] + w\n",
    "                if new_d<dis[y]:\n",
    "                    dis[y] = new_d\n",
    "                    heappush(h, (new_d, y))\n",
    "        return dis"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        graph = defaultdict(list)\n",
    "        for u,v,cnt in edges:\n",
    "            graph[u].append((v,1+cnt))\n",
    "            graph[v].append((u,1+cnt))\n",
    "        \n",
    "        queue = [(0,0)]\n",
    "        dist = [float('inf')]*n\n",
    "        dist[0] = 0\n",
    "        while queue:\n",
    "            dis,x = heapq.heappop(queue)\n",
    "            if dist[x]<dis:\n",
    "                continue\n",
    "            for nextN,nextD in graph[x]:\n",
    "                if dis+nextD < dist[nextN]:\n",
    "                    dist[nextN] = dis + nextD\n",
    "                    heapq.heappush(queue, (dist[nextN],nextN))\n",
    "            pass\n",
    "        \n",
    "        total = 0\n",
    "        for i in range(n):\n",
    "            if dist[i]<=maxMoves:\n",
    "                total += 1\n",
    "        for u,v,cnt in edges:\n",
    "            if dist[u]>maxMoves and dist[v]>maxMoves:\n",
    "                pass\n",
    "            elif dist[u]>maxMoves:\n",
    "                total += (maxMoves - dist[v])\n",
    "            elif dist[v]>maxMoves:\n",
    "                total += (maxMoves - dist[u])\n",
    "            else:\n",
    "                total += min(cnt, maxMoves*2-dist[u]-dist[v])\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v, cnt in edges:\n",
    "            g[u].append((v, cnt + 1))\n",
    "            g[v].append((u, cnt + 1))\n",
    "        dis = [inf] * n\n",
    "        dis[0] = 0\n",
    "        h = [(0, 0)]\n",
    "        while h:\n",
    "            d, x = heappop(h)\n",
    "            if d > dis[x]:\n",
    "                continue\n",
    "            for y, wt in g[x]:\n",
    "                if dis[x] + wt < dis[y]:\n",
    "                    dis[y] = dis[x] + wt\n",
    "                    heappush(h, (dis[y], y))\n",
    "        ans = sum(d <= maxMoves for d in dis)\n",
    "        for u, v, cnt in edges:\n",
    "            a = max(maxMoves - dis[u], 0)\n",
    "            b = max(maxMoves - dis[v], 0)\n",
    "            ans += min(a + b, cnt)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        graph = defaultdict(list)\n",
    "        for u,v,cnt in edges:\n",
    "            graph[u].append((v,1+cnt))\n",
    "            graph[v].append((u,1+cnt))\n",
    "        \n",
    "        queue = [(0,0)]\n",
    "        dist = [float('inf')]*n\n",
    "        dist[0] = 0\n",
    "        while queue:\n",
    "            dis,x = heapq.heappop(queue)\n",
    "            if dist[x]<dis:\n",
    "                continue\n",
    "            for nextN,nextD in graph[x]:\n",
    "                if dis+nextD < dist[nextN]:\n",
    "                    dist[nextN] = dis + nextD\n",
    "                    heapq.heappush(queue, (dist[nextN],nextN))\n",
    "            pass\n",
    "        \n",
    "        total = 0\n",
    "        for i in range(n):\n",
    "            if dist[i]<=maxMoves:\n",
    "                total += 1\n",
    "        for u,v,cnt in edges:\n",
    "            if dist[u]==float('inf') or dist[v]==float('inf'):\n",
    "                pass\n",
    "            elif dist[u]>maxMoves and dist[v]>maxMoves:\n",
    "                pass\n",
    "            elif dist[u]>maxMoves:\n",
    "                total += (maxMoves - dist[v])\n",
    "            elif dist[v]>maxMoves:\n",
    "                total += (maxMoves - dist[u])\n",
    "            else:\n",
    "                if abs(dist[u]-dist[v])==1+cnt:\n",
    "                    total += cnt\n",
    "                else:\n",
    "                    total += min(cnt, maxMoves*2-dist[u]-dist[v])\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for u, v, cnt in edges:\n",
    "            g[u].append((v, cnt + 1))\n",
    "            g[v].append((u, cnt + 1))\n",
    "        q = [(0, 0)]\n",
    "        dist = [0] + [inf] * n\n",
    "        while q:\n",
    "            d, u = heappop(q)\n",
    "            for v, cnt in g[u]:\n",
    "                if (t := d + cnt) < dist[v]:\n",
    "                    dist[v] = t\n",
    "                    q.append((t, v))\n",
    "        ans = sum(d <= maxMoves for d in dist)\n",
    "        for u, v, cnt in edges:\n",
    "            a = min(cnt, max(0, maxMoves - dist[u]))\n",
    "            b = min(cnt, max(0, maxMoves - dist[v]))\n",
    "            ans += min(cnt, a + b)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        graph = defaultdict(list)\n",
    "        for u,v,cnt in edges:\n",
    "            graph[u].append((v,1+cnt))\n",
    "            graph[v].append((u,1+cnt))\n",
    "        \n",
    "        queue = [(0,0)]\n",
    "        dist = [float('inf')]*n\n",
    "        dist[0] = 0\n",
    "        while queue:\n",
    "            dis,x = heapq.heappop(queue)\n",
    "            if dist[x]<dis:\n",
    "                continue\n",
    "            for nextN,nextD in graph[x]:\n",
    "                if dis+nextD < dist[nextN]:\n",
    "                    dist[nextN] = dis + nextD\n",
    "                    heapq.heappush(queue, (dist[nextN],nextN))\n",
    "            pass\n",
    "        \n",
    "        total = 0\n",
    "        for i in range(n):\n",
    "            if dist[i]<=maxMoves:\n",
    "                total += 1\n",
    "        for u,v,cnt in edges:\n",
    "            if dist[u]>maxMoves and dist[v]>maxMoves:\n",
    "                pass\n",
    "            elif dist[u]>maxMoves:\n",
    "                total += (maxMoves - dist[v])\n",
    "            elif dist[v]>maxMoves:\n",
    "                total += (maxMoves - dist[u])\n",
    "            else:\n",
    "                total += min(cnt, maxMoves*2-dist[u]-dist[v])\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y, w in edges:\n",
    "            g[x].append((y, w + 1))\n",
    "            g[y].append((x, w + 1))\n",
    "\n",
    "        dis = [0] + [inf] * (n - 1)\n",
    "        vis = [False] * n \n",
    "        while True:\n",
    "            x = -1\n",
    "            for i in range(n):\n",
    "                if not vis[i] and (x < 0 or dis[i] < dis[x]):\n",
    "                    x = i \n",
    "            if x == -1: break\n",
    "            vis[x] = True\n",
    "            for y, w in g[x]:\n",
    "                if dis[x] + w < dis[y]:\n",
    "                    dis[y] = dis[x] + w\n",
    "\n",
    "        print(dis)\n",
    "        ans = sum(d <= maxMoves for d in dis)\n",
    "\n",
    "        for x, y, w in edges:\n",
    "            a = max(maxMoves - dis[x], 0)\n",
    "            b = max(maxMoves - dis[y], 0)\n",
    "            ans += min(a + b, w)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "import sys\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: [[int]], maxMoves: int, n: int) -> int:\n",
    "\n",
    "        dct = defaultdict(dict)\n",
    "        for a, b, p in edges:  # flights=[ [src,dst, cost] ]\n",
    "            dct[a][b] = p+1\n",
    "            dct[b][a] = p + 1\n",
    "\n",
    "        visit = [sys.maxsize] * n  # 设置已经访问过的节点的最小距离\n",
    "        stack = [[0, 0]]  # 最短路径，当前位置，途径点数目\n",
    "        heapq.heapify(stack)\n",
    "        while stack:\n",
    "            cost, pos = heapq.heappop(stack)\n",
    "#            print(cost,pos)\n",
    "\n",
    "            if cost >= visit[pos]:  # 途径点个数超过以前访问该节点时候的途经点个数，或者途径点的个数已经超过k， 防止重复访问\n",
    "                continue\n",
    "\n",
    "            visit[pos]=min(visit[pos],cost)\n",
    "            for nex in dct[pos]:\n",
    "                if cost + dct[pos][nex]<=maxMoves:\n",
    "                    heapq.heappush(stack, [cost + dct[pos][nex], nex])  # 找到所有下一个可以到达的节点， 计算cost和途经点个数\n",
    "\n",
    "#        print(visit)\n",
    "\n",
    "        tot=0\n",
    "        for xx,yy,points in edges:\n",
    "            fromx=max(maxMoves-visit[xx],0)\n",
    "            fromy=max(maxMoves-visit[yy],0)\n",
    "            cover=min(fromx+fromy,dct[xx][yy]-1)\n",
    "            tot+=cover\n",
    "#            print(xx,yy,fromx,fromy,cover)\n",
    "\n",
    "        for i in range(n):\n",
    "            if visit[i]<=maxMoves: tot+=1\n",
    "\n",
    "        return tot\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        # 1. O(V+E) build adjacency list of undirected graph\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v, cnt in edges:\n",
    "            g[u].append((v, cnt + 1))\n",
    "            g[v].append((u, cnt + 1))\n",
    "\n",
    "        # 2. O(kE) run SPFA\n",
    "        dist = self.SPFA(0, g)\n",
    "\n",
    "        # 3. find reachable vertices by traversing all the vertices\n",
    "        ans = sum(d <= maxMoves for d in dist)  # reachable original vertices\n",
    "        for u, v, cnt in edges:\n",
    "            u_cnt = max(0, maxMoves - dist[u])  # reachable from vertex u on edge u-v\n",
    "            v_cnt = max(0, maxMoves - dist[v]) # reachable from vertex v on edge u-v\n",
    "            ans += min(cnt, u_cnt + v_cnt)  # take intersection of two sets\n",
    "        return ans\n",
    "\n",
    "    def SPFA(self, start_node: int, g: List[List[int]]) -> List[int]:\n",
    "        def relax(u: int, v: int, w: int) -> None:\n",
    "            if dist[v] > (d := dist[u] + w):\n",
    "                dist[v] = d \n",
    "                if not in_queue[v]:\n",
    "                    queue.append(v)\n",
    "                    in_queue[v] = True\n",
    "        \n",
    "        n = len(g)\n",
    "        dist = [math.inf] * n\n",
    "        dist[start_node] = 0\n",
    "        in_queue = [False] * n\n",
    "        queue = deque([start_node])\n",
    "        in_queue[start_node] = True\n",
    "        while queue:\n",
    "            u = queue.popleft()\n",
    "            in_queue[u] = False \n",
    "            for v, w in g[u]:\n",
    "                relax(u, v, w)\n",
    "        return dist\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        # 1. O(V+E) build adjacency list of undirected graph\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v, cnt in edges:\n",
    "            g[u].append((v, cnt + 1))\n",
    "            g[v].append((u, cnt + 1))\n",
    "\n",
    "        # 2. O((V+E)logV) run heap-optimized Dijkstra's algorithm\n",
    "        dist = self.Dijkstra(0, g)\n",
    "\n",
    "        # 3. find reachable vertices by traversing all the vertices\n",
    "        ans = sum(d <= maxMoves for d in dist)  # reachable original vertices\n",
    "        for u, v, cnt in edges:\n",
    "            u_cnt = max(0, maxMoves - dist[u])  # reachable from vertex u on edge u-v\n",
    "            v_cnt = max(0, maxMoves - dist[v]) # reachable from vertex v on edge u-v\n",
    "            ans += min(cnt, u_cnt + v_cnt)  # take intersection of two sets\n",
    "        return ans\n",
    "\n",
    "    def Dijkstra(self, start_node: int, g: List[List[int]]) -> List[int]:\n",
    "        def relax(u: int, v: int, w: int) -> None:\n",
    "            if dist[v] > (d := dist[u] + w):\n",
    "                dist[v] = d \n",
    "                heapq.heappush(pq, (d, v))\n",
    "\n",
    "        n = len(g)\n",
    "        dist = [math.inf] * n  \n",
    "        dist[start_node] = 0 \n",
    "        pq = [(0, start_node)]  # min-heap\n",
    "        while pq:\n",
    "            d, u = heapq.heappop(pq)\n",
    "            if d > dist[u]:    \n",
    "                continue\n",
    "    \n",
    "            for v, w in g[u]:\n",
    "                relax(u, v, w)\n",
    "        return dist\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        graph = defaultdict(list)\n",
    "        for u,v,cnt in edges:\n",
    "            graph[u].append((v,1+cnt))\n",
    "            graph[v].append((u,1+cnt))\n",
    "        \n",
    "        queue = [(0,0)]\n",
    "        dist = [float('inf')]*n\n",
    "        dist[0] = 0\n",
    "        while queue:\n",
    "            dis,x = heapq.heappop(queue)\n",
    "            if dist[x]<dis:\n",
    "                continue\n",
    "            for nextN,nextD in graph[x]:\n",
    "                if dis+nextD < dist[nextN]:\n",
    "                    dist[nextN] = dis + nextD\n",
    "                    heapq.heappush(queue, (dist[nextN],nextN))\n",
    "            pass\n",
    "        \n",
    "        total = 0\n",
    "        for i in range(n):\n",
    "            if dist[i]<=maxMoves:\n",
    "                total += 1\n",
    "        for u,v,cnt in edges:\n",
    "            if dist[u]>maxMoves and dist[v]>maxMoves:\n",
    "                pass\n",
    "            elif dist[u]>maxMoves:\n",
    "                total += (maxMoves - dist[v])\n",
    "            elif dist[v]>maxMoves:\n",
    "                total += (maxMoves - dist[u])\n",
    "            else:\n",
    "                total += min(cnt, maxMoves*2-dist[u]-dist[v])\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "原来的边可以新增节点？\n",
    "细分后。。。替换成cnt+1条边，共cnt+2个节点\n",
    "乍一看，需要维护到达每个新节点的最短距离\n",
    "\n",
    "是一个非常复杂的图\n",
    "朴素的bfs跑不动\n",
    "所以，最好不要考虑新增的节点，一旦考虑连建图都见不出来了\n",
    "修改边权跑dij，跑完后遍历每条边，计算这些边上有多少可达节点\n",
    "稠密图，用n^2算法\n",
    "\n",
    "'''\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        g=[[]*n for _ in range(n)]\n",
    "        for x,y,w in edges:\n",
    "            g[x].append((y,w+1))\n",
    "            g[y].append((x,w+1))\n",
    "        dis=[inf]*n\n",
    "        vis=[False]*n\n",
    "        dis[0]=0\n",
    "        #不能用bfs了，悲\n",
    "        '''\n",
    "        while True:\n",
    "            mn=inf\n",
    "            for i in range(n):\n",
    "                if dis[i]<mn and not vis[i]:\n",
    "                    mn=dis[i]\n",
    "                    x=i\n",
    "            if mn==inf:\n",
    "                break\n",
    "            #将与x相邻的边松弛\n",
    "            vis[x]=True\n",
    "            for y,w in g[x]:\n",
    "                if dis[y]>dis[x]+w:\n",
    "                    dis[y]=dis[x]+w\n",
    "        '''\n",
    "        h=[(0,0)]\n",
    "        while h:\n",
    "            d,x=heappop(h)  \n",
    "            if d>dis[x]:\n",
    "                continue #因为同一个点会多次入堆\n",
    "            for y,w in g[x]:\n",
    "                if dis[x]+w<dis[y]:\n",
    "                    dis[y]=dis[x]+w\n",
    "                    heappush(h,(dis[x]+w,y))\n",
    "        ans=0\n",
    "        for x in dis:\n",
    "            if x<=maxMoves:\n",
    "                ans+=1\n",
    "        #如何避免重复计算？\n",
    "        for x,y,w in edges:\n",
    "            dx,dy=dis[x],dis[y]\n",
    "            #下标从1开始一直到w\n",
    "            farx=min(maxMoves-dx,w) if dx<maxMoves else 0\n",
    "            fary=min(maxMoves-dy,w) if dy<maxMoves else 0\n",
    "            ans+=min(farx+fary,w)\n",
    "        return ans\n",
    "            \n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for u,v,cnt in edges:\n",
    "            g[u].append((v,cnt + 1))\n",
    "            g[v].append((u,cnt + 1))\n",
    "        q = [(0,0)]\n",
    "        dis = [inf]*n\n",
    "        dis[0] = 0\n",
    "        while q:\n",
    "            d,i = heappop(q)\n",
    "            if dis[i] < d:\n",
    "                continue\n",
    "            for j,w in g[i]:\n",
    "                new_d = dis[i] + w\n",
    "                #print(new_d,dis[j])\n",
    "                if new_d < dis[j]:\n",
    "                    dis[j] = new_d\n",
    "                    heappush(q,(new_d,j))\n",
    "        \n",
    "        ans = sum(d <= maxMoves for d in dis)\n",
    "        for u,v,cnt in edges:\n",
    "            a,b = max(maxMoves - dis[u],0),max(maxMoves - dis[v],0)\n",
    "            ans += min(a + b,cnt)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        graph = defaultdict(list)\n",
    "        for u,v,cnt in edges:\n",
    "            graph[u].append((v,1+cnt))\n",
    "            graph[v].append((u,1+cnt))\n",
    "        \n",
    "        queue = [(0,0)]\n",
    "        dist = [float('inf')]*n\n",
    "        dist[0] = 0\n",
    "        while queue:\n",
    "            dis,x = heapq.heappop(queue)\n",
    "            if dist[x]<dis:\n",
    "                continue\n",
    "            for nextN,nextD in graph[x]:\n",
    "                if dis+nextD < dist[nextN]:\n",
    "                    dist[nextN] = dis + nextD\n",
    "                    heapq.heappush(queue, (dist[nextN],nextN))\n",
    "            pass\n",
    "        \n",
    "        total = 0\n",
    "        for i in range(n):\n",
    "            if dist[i]<=maxMoves:\n",
    "                total += 1\n",
    "        for u,v,cnt in edges:\n",
    "            if dist[u]==float('inf') or dist[v]==float('inf'):\n",
    "                pass\n",
    "            elif dist[u]>maxMoves and dist[v]>maxMoves:\n",
    "                pass\n",
    "            elif dist[u]>maxMoves:\n",
    "                total += (maxMoves - dist[v])\n",
    "            elif dist[v]>maxMoves:\n",
    "                total += (maxMoves - dist[u])\n",
    "            else:\n",
    "                if abs(dist[u]-dist[v])==1+cnt:\n",
    "                    total += cnt\n",
    "                else:\n",
    "                    total += min(cnt, maxMoves*2-dist[u]-dist[v])\n",
    "                    # total += (maxMoves - dist[u])\n",
    "                    # total += (maxMoves - dist[v])\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "import math\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def build_graph(self, edges: List[List[int]]) -> defaultdict:\n",
    "        graph = collections.defaultdict(list)\n",
    "        for u, v, w in edges:\n",
    "            graph[u].append([v, w + 1])\n",
    "            graph[v].append([u, w + 1])\n",
    "        return graph\n",
    "\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        graph = self.build_graph(edges)\n",
    "\n",
    "        dist = [math.inf] * n\n",
    "        heap = [(0, 0)]\n",
    "        while heap:\n",
    "            (cost, u) = heapq.heappop(heap)\n",
    "            if u > maxMoves:\n",
    "                break\n",
    "            if not math.isinf(dist[u]):\n",
    "                continue\n",
    "            dist[u] = cost\n",
    "            for v, w in graph[u]:\n",
    "                if not math.isinf(dist[v]):\n",
    "                    continue\n",
    "                heapq.heappush(heap, (cost+w, v))\n",
    "\n",
    "        count = 0\n",
    "        for i in range(n):\n",
    "            count += 1 if dist[i] <= maxMoves else 0\n",
    "        for u, v, w in edges:\n",
    "            count += min(max(maxMoves - dist[u], 0) + max(maxMoves - dist[v], 0), w)\n",
    "\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for e in edges:\n",
    "            print(e)\n",
    "            ### 注意有关图的声明与处理要灵活应变！！！\n",
    "            g[e[0]].append([e[1],e[2]+1])\n",
    "            g[e[1]].append([e[0],e[2]+1])\n",
    "        #print(g)\n",
    "        #visit = defaultdict()\n",
    "        q = []\n",
    "        q.append((0,0))\n",
    "        dist = [0] + [inf] * (n)\n",
    "        ###这段的本质是求两点之间的最短路径！！！\n",
    "        while q:\n",
    "            ### 注意可以从小到大求解！！！利用小根堆！！！因为优先排序是根据第一个元素，所以此处将值放在第一位，这在后续的处理中要小心！！！别与构图g弄混！！！\n",
    "            ###注意！！！！！！headpop必须对应的是列表！！！list!!!\n",
    "            hp, cur = heappop(q)\n",
    "            ### 注意看好这个图对应的是什么，节点在前还是值在前，不要与q中的排列布局弄混！！！\n",
    "            for nxt,hpp in g[cur]:\n",
    "                ### 此处相当于找最短路径，根本不涉及maxMoves的判断与限制，因此在后期的答案的处理中要涉及此限制！\n",
    "                if hp + hpp < dist[nxt]:\n",
    "                    dist[nxt] = hp + hpp\n",
    "                    ###  此处要小心注意！！\n",
    "                    q.append((hp + hpp, nxt))\n",
    "        ### 巧用python相关函数\n",
    "        ans = sum(d <= maxMoves for d in dist)\n",
    "        for e in edges:\n",
    "            ### 这是从不同方向进行考虑！\n",
    "            u = min(e[2], max(0,maxMoves - dist[e[0]]))\n",
    "            v = min(e[2], max(0,maxMoves - dist[e[1]]))\n",
    "            ans += min(e[2], u + v)\n",
    "        \n",
    "        #别最后忘了return！！！\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        graph = defaultdict(list)\n",
    "        for u,v,cnt in edges:\n",
    "            graph[u].append((v,1+cnt))\n",
    "            graph[v].append((u,1+cnt))\n",
    "        \n",
    "        queue = [(0,0)]\n",
    "        dist = [float('inf')]*n\n",
    "        dist[0] = 0\n",
    "        while queue:\n",
    "            dis,x = heapq.heappop(queue)\n",
    "            if dist[x]<dis:\n",
    "                continue\n",
    "            for nextN,nextD in graph[x]:\n",
    "                if dis+nextD < dist[nextN]:\n",
    "                    dist[nextN] = dis + nextD\n",
    "                    heapq.heappush(queue, (dist[nextN],nextN))\n",
    "            pass\n",
    "        \n",
    "        total = 0\n",
    "        for i in range(n):\n",
    "            if dist[i]<=maxMoves:\n",
    "                total += 1\n",
    "        for u,v,cnt in edges:\n",
    "            if dist[u]>maxMoves and dist[v]>maxMoves:\n",
    "                pass\n",
    "            elif dist[u]>maxMoves:\n",
    "                total += (maxMoves - dist[v])\n",
    "            elif dist[v]>maxMoves:\n",
    "                total += (maxMoves - dist[u])\n",
    "            else:\n",
    "                total += min(cnt, maxMoves*2-dist[u]-dist[v])\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def ac_max(a, b):\n",
    "    return a if a > b else b\n",
    "\n",
    "\n",
    "def ac_min(a, b):\n",
    "    return a if a < b else b\n",
    "\n",
    "class Dijkstra:\n",
    "    def __init__(self):\n",
    "        return\n",
    "\n",
    "    @staticmethod\n",
    "    def get_dijkstra_result(dct: List[List[int]], src: int) -> List[float]:\n",
    "        # 模板: Dijkstra求最短路，变成负数求可以求最长路（还是正权值）\n",
    "        n = len(dct)\n",
    "        dis = [inf]*n\n",
    "        stack = [[0, src]]\n",
    "        dis[src] = 0\n",
    "\n",
    "        while stack:\n",
    "            d, i = heapq.heappop(stack)\n",
    "            if dis[i] < d:\n",
    "                continue\n",
    "            for j, w in dct[i]:\n",
    "                dj = w + d\n",
    "                if dj < dis[j]:\n",
    "                    dis[j] = dj\n",
    "                    heapq.heappush(stack, [dj, j])\n",
    "        return dis\n",
    "    \n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        dct = [[] for _ in range(n)]\n",
    "        for i, j, c in edges:\n",
    "            dct[i].append([j, c+1])\n",
    "            dct[j].append([i, c+1])\n",
    "        \n",
    "        dis  =Dijkstra().get_dijkstra_result(dct, 0)\n",
    "        \n",
    "        ans = sum(dis[i]<=maxMoves for i in range(n))\n",
    "        for i, j, c in edges:\n",
    "            if c:\n",
    "                if dis[i] <= maxMoves:\n",
    "                    left = ac_min(maxMoves - dis[i], c)\n",
    "                else:\n",
    "                    left = 0\n",
    "                \n",
    "                if dis[j] <= maxMoves:\n",
    "                    right = ac_min(maxMoves - dis[j], c)\n",
    "                else:\n",
    "                    right = 0\n",
    "                \n",
    "                if left+right<=c:\n",
    "                    ans += left+right\n",
    "                else:\n",
    "                    ans += c\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        graph = defaultdict(list)\n",
    "        for u,v,cnt in edges:\n",
    "            graph[u].append((v,1+cnt))\n",
    "            graph[v].append((u,1+cnt))\n",
    "        \n",
    "        queue = [(0,0)]\n",
    "        dist = [float('inf')]*n\n",
    "        dist[0] = 0\n",
    "        while queue:\n",
    "            dis,x = heapq.heappop(queue)\n",
    "            if dist[x]<dis:\n",
    "                continue\n",
    "            for nextN,nextD in graph[x]:\n",
    "                if dis+nextD < dist[nextN]:\n",
    "                    dist[nextN] = dis + nextD\n",
    "                    heapq.heappush(queue, (dist[nextN],nextN))\n",
    "            pass\n",
    "        \n",
    "        total = 0\n",
    "        for i in range(n):\n",
    "            if dist[i]<=maxMoves:\n",
    "                total += 1\n",
    "        for u,v,cnt in edges:\n",
    "            if dist[u]==float('inf') or dist[v]==float('inf'):\n",
    "                pass\n",
    "            elif dist[u]>maxMoves and dist[v]>maxMoves:\n",
    "                pass\n",
    "            elif dist[u]>maxMoves:\n",
    "                total += (maxMoves - dist[v])\n",
    "            elif dist[v]>maxMoves:\n",
    "                total += (maxMoves - dist[u])\n",
    "            else:\n",
    "                if abs(dist[u]-dist[v])==1+cnt:\n",
    "                    total += cnt\n",
    "                else:\n",
    "                    total += min(cnt, maxMoves*2-dist[u]-dist[v])\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        graph = collections.defaultdict(list)\n",
    "        for a, b, c in edges:\n",
    "            graph[a].append([b, c + 1])\n",
    "            graph[b].append([a, c + 1])\n",
    "        dis = [float('inf')] * n \n",
    "        dis[0] = 0\n",
    "        queue = collections.deque([0])\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            for nei, cost in graph[cur]:\n",
    "                if dis[nei] > dis[cur] + cost:\n",
    "                    dis[nei] = dis[cur] + cost \n",
    "                    queue.append(nei)\n",
    "        res = 0\n",
    "        for a, b, c in edges:\n",
    "            res += min(c, max(maxMoves - dis[a], 0) + max(maxMoves - dis[b], 0))\n",
    "        for node in range(n):\n",
    "            if dis[node] <= maxMoves:\n",
    "                res += 1 \n",
    "        return res \n",
    "\n",
    "\n",
    "     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        g = defaultdict(dict)\n",
    "        for x, y, c in edges:\n",
    "            g[x][y] = g[y][x] = c\n",
    "        dist = [-1] * n\n",
    "        dist[0] = maxMoves\n",
    "        h = [(-maxMoves, 0)]\n",
    "        ans = 0\n",
    "        while h:\n",
    "            v, x = heappop(h)\n",
    "            v *= -1\n",
    "            if v < dist[x]: continue\n",
    "            ans += 1\n",
    "            for y, c in g[x].items():\n",
    "                if v >= c + 1:\n",
    "                    ans += c\n",
    "                    if v - c - 1 > dist[y]:\n",
    "                        dist[y] = v - c - 1\n",
    "                        heappush(h, (c + 1 - v, y))\n",
    "                    g[y][x] = 0\n",
    "                elif v < c + 1:\n",
    "                    ans += v\n",
    "                    g[y][x] -= v\n",
    "        \n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def ac_max(a, b):\n",
    "    return a if a > b else b\n",
    "\n",
    "\n",
    "def ac_min(a, b):\n",
    "    return a if a < b else b\n",
    "\n",
    "class Dijkstra:\n",
    "    def __init__(self):\n",
    "        return\n",
    "\n",
    "    @staticmethod\n",
    "    def get_dijkstra_result(dct: List[List[int]], src: int) -> List[float]:\n",
    "        # 模板: Dijkstra求最短路，变成负数求可以求最长路（还是正权值）\n",
    "        n = len(dct)\n",
    "        dis = [inf]*n\n",
    "        stack = [[0, src]]\n",
    "        dis[src] = 0\n",
    "\n",
    "        while stack:\n",
    "            d, i = heapq.heappop(stack)\n",
    "            if dis[i] < d:\n",
    "                continue\n",
    "            for j, w in dct[i]:\n",
    "                dj = w + d\n",
    "                if dj < dis[j]:\n",
    "                    dis[j] = dj\n",
    "                    heapq.heappush(stack, [dj, j])\n",
    "        return dis\n",
    "    \n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        dct = [[] for _ in range(n)]\n",
    "        for i, j, c in edges:\n",
    "            dct[i].append([j, c+1])\n",
    "            dct[j].append([i, c+1])\n",
    "        \n",
    "        dis  =Dijkstra().get_dijkstra_result(dct, 0)\n",
    "        \n",
    "        ans = sum(dis[i] <= maxMoves for i in range(n))\n",
    "        for i, j, c in edges:\n",
    "            if c:\n",
    "                if dis[i] <= maxMoves:\n",
    "                    a, b = maxMoves - dis[i], c\n",
    "                    left = a if a < b else b\n",
    "                else:\n",
    "                    left = 0\n",
    "                \n",
    "                if dis[j] <= maxMoves:\n",
    "                    a, b = maxMoves - dis[j], c\n",
    "                    right = a if a < b else b\n",
    "                else:\n",
    "                    right = 0\n",
    "                \n",
    "                if left+right <= c:\n",
    "                    ans += left+right\n",
    "                else:\n",
    "                    ans += c\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        graph = defaultdict(list)\n",
    "        for u, v, nodes in edges:\n",
    "            graph[u].append((v, nodes+1))\n",
    "            graph[v].append((u, nodes+1))\n",
    "        \n",
    "        dist = [inf]*n\n",
    "        seen = set()\n",
    "        dist[0] = 0\n",
    "        q = [(0, 0)]\n",
    "        while q:\n",
    "            dst, u = heapq.heappop(q)\n",
    "            if u in seen:\n",
    "                continue\n",
    "            seen.add(u)\n",
    "            for v, distance in graph[u]:\n",
    "                if dist[u]+distance < dist[v]:\n",
    "                    dist[v] = dist[u]+distance\n",
    "                    heapq.heappush(q, (dist[v], v))\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if dist[i] <=maxMoves:\n",
    "                ans += 1\n",
    "        for u, v, edge in edges:\n",
    "            t1 = max(0, maxMoves-dist[u])\n",
    "            t2 = max(0, maxMoves-dist[v])\n",
    "            ans += min(edge, t1+t2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for e in edges:\n",
    "            print(e)\n",
    "            ### 注意有关图的声明与处理要灵活应变！！！\n",
    "            g[e[0]].append([e[1],e[2]+1])\n",
    "            g[e[1]].append([e[0],e[2]+1])\n",
    "        #print(g)\n",
    "        #visit = defaultdict()\n",
    "        q = []\n",
    "        q.append((0,0))\n",
    "        dist = [0] + [inf] * (n-1)\n",
    "        ###这段的本质是求两点之间的最短路径！！！\n",
    "        while q:\n",
    "            ### 注意可以从小到大求解！！！利用小根堆！！！因为优先排序是根据第一个元素，所以此处将值放在第一位，这在后续的处理中要小心！！！别与构图g弄混！！！\n",
    "            ###注意！！！！！！headpop必须对应的是列表！！！list!!!\n",
    "            hp, cur = heappop(q)\n",
    "            ### 注意看好这个图对应的是什么，节点在前还是值在前，不要与q中的排列布局弄混！！！\n",
    "            for nxt,hpp in g[cur]:\n",
    "                ### 此处相当于找最短路径，根本不涉及maxMoves的判断与限制，因此在后期的答案的处理中要涉及此限制！\n",
    "                if hp + hpp < dist[nxt]:\n",
    "                    dist[nxt] = hp + hpp\n",
    "                    ###  此处要小心注意！！\n",
    "                    q.append((hp + hpp, nxt))\n",
    "        ### 巧用python相关函数\n",
    "        ans = sum(d <= maxMoves for d in dist)\n",
    "        for e in edges:\n",
    "            ### 这是从不同方向进行考虑！\n",
    "            u = min(e[2], max(0,maxMoves - dist[e[0]]))\n",
    "            v = min(e[2], max(0,maxMoves - dist[e[1]]))\n",
    "            ans += min(e[2], u + v)\n",
    "        \n",
    "        #别最后忘了return！！！\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v, cnt in edges:\n",
    "            g[u].append((v, cnt + 1))\n",
    "            g[v].append((u, cnt + 1))  # 建图\n",
    "\n",
    "        print(g)\n",
    "        dist = [inf] * n\n",
    "        vis = [False] * n\n",
    "        dist[0] = 0\n",
    "\n",
    "        for _ in range(n):\n",
    "            x = -1\n",
    "            for i in range(n):\n",
    "                if not vis[i] and (x == -1 or dist[i] < dist[x]):\n",
    "                    x = i\n",
    "            \n",
    "            vis[x] = True\n",
    "            for y, q in enumerate(g[x]):\n",
    "                \n",
    "                if dist[x] + q[1] < dist[q[0]]:\n",
    "                    dist[q[0]] = dist[x] + q[1]\n",
    "        print(dist)\n",
    "        \n",
    "        ans = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            if dist[i] <= maxMoves:\n",
    "                ans += 1\n",
    "        for u, v, cnt in edges:\n",
    "            a = max(maxMoves - dist[u], 0)\n",
    "            b = max(maxMoves - dist[v], 0)\n",
    "            \n",
    "            ans += min(a + b, cnt)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "import math\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def build_graph(self, edges: List[List[int]]) -> defaultdict:\n",
    "        graph = collections.defaultdict(list)\n",
    "        for u, v, w in edges:\n",
    "            graph[u].append([v, w + 1])\n",
    "            graph[v].append([u, w + 1])\n",
    "        return graph\n",
    "\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        graph = self.build_graph(edges)\n",
    "\n",
    "        dist = [math.inf] * n\n",
    "        heap = [(0, 0)]\n",
    "        while heap:\n",
    "            (cost, u) = heapq.heappop(heap)\n",
    "            if not math.isinf(dist[u]):\n",
    "                continue\n",
    "            dist[u] = cost\n",
    "            for v, w in graph[u]:\n",
    "                if not math.isinf(dist[v]):\n",
    "                    continue\n",
    "                heapq.heappush(heap, (cost+w, v))\n",
    "\n",
    "        count = 0\n",
    "        for i in range(n):\n",
    "            count += 1 if dist[i] <= maxMoves else 0\n",
    "        for u, v, w in edges:\n",
    "            count += min(max(maxMoves - dist[u], 0) + max(maxMoves - dist[v], 0), w)\n",
    "\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        # 获取所有点的最短路路径\n",
    "        # 查看所有的双向边，根据边的子节点数和两个端点的最短距离以及maxMoves判断边上有多少子节点可以访问\n",
    "        can_move = {}\n",
    "        visit_edge = set()\n",
    "        min_distance = {}\n",
    "        for edge in edges:\n",
    "            if edge[0] not in can_move.keys():\n",
    "                can_move[edge[0]] = {}\n",
    "            can_move[edge[0]][edge[1]] = edge[2]\n",
    "            if edge[1] not in can_move.keys():\n",
    "                can_move[edge[1]] = {}\n",
    "            can_move[edge[1]][edge[0]] = edge[2]\n",
    "        \n",
    "        queue = [{\"point\": 0, \"min_dis\": 0}]\n",
    "        for i in range(1, n):\n",
    "            queue.append({\"point\": i, \"min_dis\": 10**20})\n",
    "        get_min_dis = set()\n",
    "        while queue:\n",
    "            # 找到最短路径节点\n",
    "            min_dis = queue[0][\"min_dis\"]\n",
    "            min_pos = 0\n",
    "            for i in range(len(queue)):\n",
    "                if queue[i][\"min_dis\"] < min_dis:\n",
    "                    min_dis = queue[i][\"min_dis\"]\n",
    "                    min_pos = i\n",
    "            min_point = queue[min_pos][\"point\"]\n",
    "            min_distance[min_point] = min_dis\n",
    "            queue.pop(min_pos)\n",
    "            # 更新节点信息\n",
    "            for i in range(len(queue)):\n",
    "                if min_point in can_move and queue[i][\"point\"] in can_move[min_point] and queue[i][\"min_dis\"] > min_dis + can_move[min_point][queue[i][\"point\"]] + 1:\n",
    "                    queue[i][\"min_dis\"] = min_dis + can_move[min_point][queue[i][\"point\"]] + 1\n",
    "        res = 0\n",
    "        for p in min_distance:\n",
    "            if min_distance[p] != 10**20 and min_distance[p] <= maxMoves:\n",
    "                res += 1\n",
    "        for edge in edges:\n",
    "            if maxMoves - min_distance[edge[0]] >= edge[2] or maxMoves - min_distance[edge[1]] >= edge[2]:\n",
    "                res += edge[2]\n",
    "            elif maxMoves - min_distance[edge[0]] + maxMoves - min_distance[edge[1]] >= edge[2]:\n",
    "                res += edge[2]\n",
    "            else:\n",
    "                if maxMoves > min_distance[edge[0]]:\n",
    "                    res += maxMoves - min_distance[edge[0]]\n",
    "                if maxMoves > min_distance[edge[1]]:\n",
    "                    res += maxMoves - min_distance[edge[1]]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v, cnt in edges:\n",
    "            g[u].append((v, cnt + 1))\n",
    "            g[v].append((u, cnt + 1))  # 建图\n",
    "        print(g)\n",
    "        dist = [inf] * n\n",
    "        vis = [False] * n\n",
    "        dist[0] = 0\n",
    "\n",
    "        start = 0\n",
    "        # 如何通过heapq来优化dijkstra算法\n",
    "        import heapq\n",
    "        h = [(0, start)]\n",
    "        while h:\n",
    "            d, x = heapq.heappop(h)\n",
    "            # if d > dist[x]:\n",
    "            #     continue\n",
    "            \n",
    "            for y, wt in g[x]:\n",
    "                newd = dist[x] + wt\n",
    "                if newd < dist[y]:\n",
    "                    dist[y] = newd\n",
    "                    heapq.heappush(h, (dist[y], y))\n",
    "        \n",
    "        print(dist)\n",
    "        ans = 0\n",
    "\n",
    "        # 计算最短路的意义，求出最短路来，就可以知道有多少个点可以算到ans里面\n",
    "        # 计算每条边上，能有多少个点\n",
    "        # 这个的要点是从起点出发\n",
    "        for i in range(n):\n",
    "            if dist[i] <= maxMoves:\n",
    "                ans += 1\n",
    "        for u, v, cnt in edges:\n",
    "            a = max(maxMoves - dist[u], 0)\n",
    "            b = max(maxMoves - dist[v], 0)\n",
    "            \n",
    "            ans += min(a + b, cnt)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v, cnt in edges:\n",
    "            g[u].append((v, cnt + 1))\n",
    "            g[v].append((u, cnt + 1))  # 建图\n",
    "        print(g)\n",
    "        dist = [inf] * n\n",
    "        vis = [False] * n\n",
    "        dist[0] = 0\n",
    "\n",
    "        start = 0\n",
    "        # 如何通过heapq来优化dijkstra算法\n",
    "        import heapq\n",
    "        h = [(0, start)]\n",
    "        while h:\n",
    "            d, x = heapq.heappop(h)\n",
    "            if d > dist[x]:\n",
    "                continue\n",
    "            \n",
    "            for y, wt in g[x]:\n",
    "                newd = dist[x] + wt\n",
    "                if newd < dist[y]:\n",
    "                    dist[y] = newd\n",
    "                    heapq.heappush(h, (dist[y], y))\n",
    "        \n",
    "        print(dist)\n",
    "        ans = 0\n",
    "\n",
    "        # 计算最短路的意义，求出最短路来，就可以知道有多少个点可以算到ans里面\n",
    "        # 计算每条边上，能有多少个点\n",
    "        # 这个的要点是从起点出发\n",
    "        for i in range(n):\n",
    "            if dist[i] <= maxMoves:\n",
    "                ans += 1\n",
    "        for u, v, cnt in edges:\n",
    "            a = max(maxMoves - dist[u], 0)\n",
    "            b = max(maxMoves - dist[v], 0)\n",
    "            \n",
    "            ans += min(a + b, cnt)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        G = [[] for _ in range(n)]\n",
    "        for u,v,w in edges:\n",
    "            G[u].append([v,w])\n",
    "            G[v].append([u,w])\n",
    "        c = Counter()\n",
    "\n",
    "        # dijkstra\n",
    "        dist = [math.inf] * n\n",
    "        dist[0] = 0\n",
    "        h = [(0,0)]\n",
    "        while h:\n",
    "            di, i = heappop(h)\n",
    "            if di != dist[i]: continue\n",
    "            if di > maxMoves: break\n",
    "            for j,w in G[i]:\n",
    "                if di + w+1 < dist[j]:\n",
    "                    dist[j] = di + w+1\n",
    "                    heappush(h, (dist[j], j))\n",
    "        \n",
    "        ans = 0\n",
    "        for i,di in enumerate(dist):\n",
    "            if di > maxMoves: continue\n",
    "            ans += 1\n",
    "            x = maxMoves - di\n",
    "            for j,w in G[i]:\n",
    "                c[(i,j)] = x\n",
    "\n",
    "        for i,j,w in edges:\n",
    "            ans += min(w, c[(i,j)] + c[(j,i)])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        connects = collections.defaultdict(dict)\n",
    "        for s, e, c in edges:\n",
    "            connects[s][e] = c\n",
    "            connects[e][s] = c\n",
    "        stack, visited, ans = [[0, 0]], set(), 0\n",
    "        cnts = {}\n",
    "        while stack:\n",
    "            val, idx = heapq.heappop(stack)\n",
    "            if not idx in visited:\n",
    "                visited.add(idx)\n",
    "                ans += 1\n",
    "                for nexti in connects[idx]:\n",
    "                    c = connects[idx][nexti]\n",
    "                    cnts[(idx, nexti)] = min(maxMoves - val, c)\n",
    "                    if maxMoves - val >=  c + 1 and not nexti in visited:\n",
    "                        heapq.heappush(stack, [val + 1 + c, nexti])\n",
    "        for i, j in cnts:\n",
    "            if i > j and (j, i) in cnts: continue\n",
    "            tmp = cnts[(i, j)]\n",
    "            if (j, i) in cnts: tmp += cnts[(j, i)]\n",
    "            ans += min(tmp, connects[i][j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# from collections import deque\r\n",
    "import heapq\r\n",
    "class Solution:\r\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\r\n",
    "\r\n",
    "        graph=[[] for _ in range(n)]\r\n",
    "        # edge_vis={}\r\n",
    "        for x,y,d in edges:\r\n",
    "            graph[x].append([y,d])\r\n",
    "            graph[y].append([x,d])\r\n",
    "        \r\n",
    "        q=[[0,0]]\r\n",
    "        ret=0\r\n",
    "        vis=set()\r\n",
    "        # dis=[0]*n\r\n",
    "        used={}\r\n",
    "        while q:\r\n",
    "            step,x =heapq.heappop(q)\r\n",
    "            if x in vis:\r\n",
    "                continue\r\n",
    "            vis.add(x)\r\n",
    "            ret+=1\r\n",
    "            for y,nodes in graph[x]:\r\n",
    "                if step+1+nodes<=maxMoves and y not in vis:\r\n",
    "                    # ret+=1\r\n",
    "                    heapq.heappush(q,[step+1+nodes,y])\r\n",
    "                used[(x,y)]=max(0,maxMoves-step)\r\n",
    "        for x,y,nodes in edges:\r\n",
    "            ret+=min(nodes,used.get((x,y),0)+used.get((y,x),0))\r\n",
    "        return ret\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        adList = defaultdict(list)\n",
    "        for u, v, nodes in edges:\n",
    "            adList[u].append([v, nodes])\n",
    "            adList[v].append([u, nodes])\n",
    "        used = {}\n",
    "        visited = set()\n",
    "        reachableNodes = 0\n",
    "        pq = [[0, 0]]\n",
    "\n",
    "        while pq and pq[0][0] <= maxMoves:\n",
    "            step, u = heapq.heappop(pq)\n",
    "            if u in visited:\n",
    "                continue\n",
    "            visited.add(u)\n",
    "            reachableNodes += 1\n",
    "            for v, nodes in adList[u]:\n",
    "                if nodes + step + 1 <= maxMoves and v not in visited:\n",
    "                    heappush(pq, [nodes + step + 1, v])\n",
    "                used[(u, v)] = min(nodes, maxMoves - step)\n",
    "\n",
    "        for u, v, nodes in edges:\n",
    "            reachableNodes += min(nodes, used.get((u, v), 0) + used.get((v, u), 0))\n",
    "        return reachableNodes\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for u, v, cnt in edges:\n",
    "            graph[u].append((v, cnt))\n",
    "            graph[v].append((u, cnt))\n",
    "\n",
    "        ans = 0\n",
    "        edge_max = collections.defaultdict(int)\n",
    "        heap = [(0, 0)]\n",
    "        min_dist = [math.inf] * n\n",
    "        while heap:\n",
    "            d, cur = heapq.heappop(heap)\n",
    "            if d >= min_dist[cur]:\n",
    "                continue\n",
    "            min_dist[cur] = d\n",
    "            ans += 1\n",
    "            for nxt, cnt in graph[cur]:\n",
    "                nd = d + cnt + 1\n",
    "                if nd <= maxMoves and nd < min_dist[nxt]:\n",
    "                    heapq.heappush(heap, (nd, nxt))\n",
    "                edge_max[(cur, nxt)] = max(edge_max[(cur, nxt)], maxMoves - d)\n",
    "\n",
    "        for u, v, cnt in edges:\n",
    "            ans += min(cnt, edge_max[(u, v)] + edge_max[(v, u)])\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        adList = defaultdict(list)\n",
    "        for u, v, nodes in edges:\n",
    "            adList[u].append([v, nodes])\n",
    "            adList[v].append([u, nodes])\n",
    "        used = {}\n",
    "        visited = set()\n",
    "        reachableNodes = 0\n",
    "        pq = [[0, 0]]\n",
    "\n",
    "        while pq and pq[0][0] <= maxMoves:\n",
    "            step, u = heapq.heappop(pq)\n",
    "            if u in visited:\n",
    "                continue\n",
    "            visited.add(u)\n",
    "            reachableNodes += 1\n",
    "            for v, nodes in adList[u]:\n",
    "                if nodes + step + 1 <= maxMoves and v not in visited:\n",
    "                    heappush(pq, [nodes + step + 1, v])\n",
    "                used[(u, v)] = min(nodes, maxMoves - step)\n",
    "\n",
    "        for u, v, nodes in edges:\n",
    "            reachableNodes += min(nodes, used.get((u, v), 0) + used.get((v, u), 0))\n",
    "        return reachableNodes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        # Store all edges according to nodes in 'neighbors'.\n",
    "        neighbors = collections.defaultdict(list)\n",
    "        for node_a, node_b in edges:\n",
    "            neighbors[node_a].append(node_b)\n",
    "            neighbors[node_b].append(node_a)\n",
    "\n",
    "        # Mark the nodes in 'restricted' as visited.\n",
    "        seen = [False] * n\n",
    "        for node in restricted:\n",
    "            seen[node] = True\n",
    "        \n",
    "        def dfs(curr_node):\n",
    "            # Mark 'curr_node' as visited and increment 'ans' by 1.\n",
    "            self.ans += 1\n",
    "            seen[curr_node] = True\n",
    "            \n",
    "            # Go for unvisited neighbors of 'currNode'.\n",
    "            for next_node in neighbors[curr_node]:\n",
    "                if not seen[next_node]:\n",
    "                    dfs(next_node)\n",
    "\n",
    "        self.ans = 0\n",
    "        dfs(0)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "        \n",
    "        s = set(restricted)\n",
    "        q = deque([0])\n",
    "        s.add(0)\n",
    "        ans = 0\n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "            ans += 1\n",
    "            for ch in g[node]:\n",
    "                if ch not in s:\n",
    "                    s.add(ch)\n",
    "                    q.append(ch)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        \n",
    "        graph = [[] for _ in range(n)]\n",
    "        for u,v in edges:\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "        \n",
    "        visited = set(restricted)       # 受限节点\n",
    "        visited.add(0)\n",
    "        \n",
    "        ans = 1\n",
    "        deque = collections.deque([0])\n",
    "        while deque:\n",
    "            \n",
    "            u = deque.popleft()\n",
    "            for v in graph[u]:\n",
    "                if v not in visited:\n",
    "                    visited.add(v)\n",
    "                    deque.append(v)\n",
    "                    ans += 1\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        # 1. O(E) build adjacency list for tree\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for u,v in edges:\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "        \n",
    "        def bfs(node: int, parent: int) -> int:\n",
    "            ans = 1 # node 0\n",
    "            queue = deque([[node, parent]])\n",
    "            while queue:\n",
    "                node, parent = queue.popleft()\n",
    "                for neighbor in graph[node]:\n",
    "                    if neighbor not in restricted and neighbor != parent:\n",
    "                        ans += 1\n",
    "                        queue.append((neighbor, node))\n",
    "\n",
    "            return ans \n",
    "        \n",
    "        # 2. BFS O(V) traverse tree\n",
    "        restricted = set(restricted)\n",
    "        ans = bfs(0, -1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i, j in edges:\n",
    "            g[i].append(j)\n",
    "            g[j].append(i)\n",
    "        \n",
    "        restricted = set(restricted)\n",
    "        vis = set()\n",
    "        ans = 0\n",
    "        queue = deque([0])\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            vis.add(node)\n",
    "            ans += 1\n",
    "            for i in g[node]:\n",
    "                if (i not in vis) and (i not in restricted):\n",
    "                    queue.append(i)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        restricted = set(restricted)\n",
    "        parentMap = list(range(n))\n",
    "        def parent(x):\n",
    "            stack = []\n",
    "            while (y:=parentMap[x]) != x:\n",
    "                stack.append(y)\n",
    "                x = y\n",
    "            for y in stack:\n",
    "                parentMap[y] = x\n",
    "            return x\n",
    "        for a, b in edges:\n",
    "            if a in restricted or b in restricted: continue\n",
    "            pa, pb = parent(a), parent(b)\n",
    "            if pa == pb: continue\n",
    "            if pa > pb:\n",
    "                pa, pb = pb, pa\n",
    "            parentMap[pb] = pa\n",
    "        return sum(1 for x in parentMap if parent(x) == 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        # 1. O(E) build adjacency list for tree\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for u,v in edges:\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "        \n",
    "        # 2. BFS O(V) traverse tree\n",
    "        visited = set(restricted)\n",
    "        visited.add(0)\n",
    "        \n",
    "        ans = 1 # node 0\n",
    "        queue = deque([[0, -1]])\n",
    "        while queue:\n",
    "            node, parent = queue.popleft()\n",
    "            for neighbor in graph[node]:\n",
    "                if neighbor not in visited:\n",
    "                    ans += 1\n",
    "                    queue.append((neighbor, node))\n",
    "                    visited.add(neighbor)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\r\n",
    "\r\n",
    "class UnionFind:\r\n",
    "    def __init__(self, n):\r\n",
    "        self.parent = list(range(n))\r\n",
    "        self.rank = [0] * n\r\n",
    "        \r\n",
    "    def find(self, x):\r\n",
    "        if self.parent[x] != x:\r\n",
    "            self.parent[x] = self.find(self.parent[x])\r\n",
    "            \r\n",
    "        return self.parent[x]\r\n",
    "\r\n",
    "    def union(self, x, y):\r\n",
    "        root_x = self.find(x)\r\n",
    "        root_y = self.find(y)\r\n",
    "        \r\n",
    "        if self.rank[root_x] > self.rank[root_y]:\r\n",
    "            self.parent[root_y] = root_x\r\n",
    "        elif self.rank[root_x] < self.rank[root_y]:\r\n",
    "            self.parent[root_x] = root_y\r\n",
    "        else:\r\n",
    "            self.parent[root_x] = root_y\r\n",
    "            self.rank[root_y] += 1\r\n",
    "        \r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\r\n",
    "        uf = UnionFind(n)\r\n",
    "        ban = set(restricted)\r\n",
    "        for x, y in edges:\r\n",
    "            if x in ban or y in ban:\r\n",
    "                continue\r\n",
    "            uf.union(x, y)\r\n",
    "        \r\n",
    "        \r\n",
    "        \r\n",
    "        return sum([uf.find(0) == uf.find(x) for x in range(n)])\r\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "\t\tif 0 in restricted:\n",
    "\t\t\treturn 0\n",
    "\t\tres = 0\n",
    "\t\tq = collections.deque([0])\n",
    "\t\tgraph = [list() for _ in range(n)]\n",
    "\n",
    "\t\tfor edge in edges: \n",
    "\t\t\tgraph[edge[0]].append(edge[1])\n",
    "\t\t\tgraph[edge[1]].append(edge[0])\n",
    "\n",
    "\t\tvis = [0 for _ in range(n)]\n",
    "\t\tvis[0] = 1\n",
    "\n",
    "\t\trecord = [0 for _ in range(n)]\n",
    "\n",
    "\t\tfor v in restricted: \n",
    "\t\t\trecord[v] = 1\n",
    "\n",
    "\t\twhile q:\n",
    "\t\t\troot = q.popleft()\n",
    "\t\t\tvis[root] = 1\n",
    "\t\t\tres += 1\n",
    "\t\t\tfor child in graph[root]:\n",
    "\t\t\t\tif not record[child] and not vis[child]:\n",
    "\t\t\t\t\tq.append(child)\n",
    "\n",
    "\t\treturn res\t\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\r\n",
    "\r\n",
    "class UnionFind:\r\n",
    "    def __init__(self, n):\r\n",
    "        self.parent = list(range(n))\r\n",
    "        self.rank = [0] * n\r\n",
    "        \r\n",
    "    def find(self, x):\r\n",
    "        if self.parent[x] != x:\r\n",
    "            self.parent[x] = self.find(self.parent[x])\r\n",
    "            \r\n",
    "        return self.parent[x]\r\n",
    "\r\n",
    "    def union(self, x, y):\r\n",
    "        root_x = self.find(x)\r\n",
    "        root_y = self.find(y)\r\n",
    "        \r\n",
    "        if self.rank[root_x] > self.rank[root_y]:\r\n",
    "            self.parent[root_y] = root_x\r\n",
    "        elif self.rank[root_x] < self.rank[root_y]:\r\n",
    "            self.parent[root_x] = root_y\r\n",
    "        else:\r\n",
    "            self.parent[root_x] = root_y\r\n",
    "            self.rank[root_y] += 1\r\n",
    "        \r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\r\n",
    "        uf = UnionFind(n)\r\n",
    "        ban = set(restricted)\r\n",
    "        for x, y in edges:\r\n",
    "            if x in ban or y in ban:\r\n",
    "                continue\r\n",
    "            uf.union(x, y)\r\n",
    "        \r\n",
    "        \r\n",
    "        \r\n",
    "        return sum([uf.find(0) == uf.find(x) for x in range(n)])\r\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        graph = [[] for _ in range(n)]\n",
    "\n",
    "        restricted = set(restricted)\n",
    "\n",
    "        for edge in edges:\n",
    "            if edge[0] in restricted or edge[1] in restricted:\n",
    "                continue\n",
    "            graph[edge[0]].append(edge[1])\n",
    "            graph[edge[1]].append(edge[0])\n",
    "        \n",
    "        ans = 0\n",
    "                \n",
    "        import queue\n",
    "\n",
    "        visited = set()\n",
    "\n",
    "        qu = queue.Queue()\n",
    "        qu.put(0)\n",
    "        ans += 1\n",
    "        visited.add(0)\n",
    "\n",
    "        while not qu.empty():\n",
    "            node = qu.get()\n",
    "            for tmp in graph[node]:\n",
    "                if tmp not in visited:\n",
    "                    qu.put(tmp)\n",
    "                    visited.add(tmp)\n",
    "                    ans += 1\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        ans = 1\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        \n",
    "        vis = set()\n",
    "        vis.add(0)\n",
    "        q = deque()\n",
    "        q.append(0)\n",
    "        restricted = set(restricted)\n",
    "        while q:\n",
    "            size = len(q)\n",
    "            for _ in range(size):\n",
    "                cur = q.popleft()\n",
    "                for nxt in g[cur]:\n",
    "                    if nxt not in vis and nxt not in restricted:\n",
    "                        q.append(nxt)\n",
    "                        vis.add(nxt)\n",
    "                        ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        ans = 1\n",
    "        q = [0]\n",
    "        vis = [False] * n \n",
    "        vis[0] = True\n",
    "        for i in restricted: vis[i] = True\n",
    "        while q:\n",
    "            tmp, q = q, []\n",
    "            for x in tmp:\n",
    "                for y in g[x]:\n",
    "                    if not vis[y]:\n",
    "                        q.append(y)\n",
    "                        vis[y] = True\n",
    "                        ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        g=[[] for _ in range(n)]\n",
    "        ans=0\n",
    "        r=set(restricted)\n",
    "        for a, b in edges:\n",
    "            if a not in r and b not in r:\n",
    "                g[a].append(b)\n",
    "                g[b].append(a)\n",
    "        q=[(0,-1)]\n",
    "        ans+=1\n",
    "        while q:\n",
    "            tmp=q\n",
    "            q=[]\n",
    "            for i,fa in tmp:\n",
    "                for j in g[i]:\n",
    "                    if j != fa:\n",
    "                        ans+=1\n",
    "                        q.append((j,i))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        g=[[] for _ in range(n)]\n",
    "        ans=0\n",
    "        r=set(restricted)\n",
    "        for a, b in edges:\n",
    "            if a not in r and b not in r:\n",
    "                g[a].append(b)\n",
    "                g[b].append(a)\n",
    "        q=[(0,-1)]\n",
    "        while q:\n",
    "            tmp=q\n",
    "            q=[]\n",
    "            for i,fa in tmp:\n",
    "                ans+=1\n",
    "                for j in g[i]:\n",
    "                    if j != fa:\n",
    "                        q.append((j,i))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        res=0\n",
    "        lst=[0 for _ in range(0,n)]\n",
    "        for i in restricted:\n",
    "            lst[i]=1\n",
    "        rt=[[] for _ in range(0,n)]\n",
    "        for i in edges:\n",
    "            rt[i[0]].append(i[1])\n",
    "            rt[i[1]].append(i[0])\n",
    "        arr=[0]\n",
    "        while arr:\n",
    "            tmp=[]\n",
    "            for i in arr:\n",
    "                if lst[i]==0:\n",
    "                    lst[i]=1\n",
    "                    res+=1\n",
    "                    for j in rt[i]:\n",
    "                        tmp.append(j)\n",
    "            arr=list(set(tmp))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        table, tag = [[] for _ in range(n)], [False for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            table[a].append(b)\n",
    "            table[b].append(a)\n",
    "        for x in restricted:\n",
    "            tag[x] = True\n",
    "        tag[0] = True\n",
    "        q, ans = deque([0]), 1\n",
    "        while len(q):\n",
    "            for x in table[q.popleft()]:\n",
    "                if tag[x] == False:\n",
    "                    tag[x] = not tag[x]\n",
    "                    q.append(x)\n",
    "                    ans += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        table, tag = [[] for _ in range(n)], [False for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            table[a].append(b)\n",
    "            table[b].append(a)\n",
    "        for x in restricted:\n",
    "            tag[x] = True\n",
    "        tag[0] = True\n",
    "        q, ans = deque([0]), 1\n",
    "        while len(q):\n",
    "            for x in table[q.popleft()]:\n",
    "                if tag[x] == False:\n",
    "                    tag[x] = not tag[x]\n",
    "                    q.append(x)\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        neighbours = [None] * n\n",
    "        for a, b in edges:\n",
    "            if neighbours[a]:\n",
    "                neighbours[a].append(b)\n",
    "            else:\n",
    "                neighbours[a] = [b]\n",
    "            if neighbours[b]:\n",
    "                neighbours[b].append(a)\n",
    "            else:\n",
    "                neighbours[b] = [a]\n",
    "        s = set(restricted)\n",
    "        visited = [False] * n\n",
    "        visited[0] = True\n",
    "        res = 1\n",
    "        p = deque([0])\n",
    "        while p:\n",
    "            a = p.popleft()\n",
    "            for b in neighbours[a]:\n",
    "                if not visited[b] and b not in s:\n",
    "                    p.append(b)\n",
    "                    visited[b] = True\n",
    "                    res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        g = [[]for _ in range(n)]\n",
    "\n",
    "        for s,e in edges:\n",
    "            g[s].append(e)\n",
    "            g[e].append(s)\n",
    "        \n",
    "        queue = [(0,-1)]\n",
    "        re = set(restricted)\n",
    "        res = 0\n",
    "        while queue:\n",
    "            cur,fa = queue.pop(0)\n",
    "            res+=1\n",
    "            for ne in g[cur]:\n",
    "                if ne not in re and ne!=fa:\n",
    "                    queue.append((ne,cur))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        route_map = dict()\n",
    "        restricted = set(restricted)\n",
    "        for i in range(n):\n",
    "            if i in restricted:\n",
    "                continue\n",
    "            route_map[i] = []\n",
    "        \n",
    "        for edge in edges:\n",
    "            if edge[0] in restricted or edge[1] in restricted:\n",
    "                continue\n",
    "            if edge[0] not in route_map[edge[1]]:\n",
    "                route_map[edge[1]].append(edge[0])\n",
    "            if edge[1] not in route_map[edge[0]]:\n",
    "                route_map[edge[0]].append(edge[1])\n",
    "        \n",
    "        result = 1\n",
    "        cur_visit, cur_value = set([0]), set(route_map[0])\n",
    "        while cur_value:\n",
    "            next_value = set()\n",
    "            for value in cur_value:\n",
    "                if value not in cur_visit:\n",
    "                    cur_visit.update([value])\n",
    "                    result += 1\n",
    "                    next_value.update(route_map[value])\n",
    "            cur_value = next_value - cur_visit\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        from collections import defaultdict\n",
    "        graph = defaultdict(list)\n",
    "        for u, v in edges:\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "\n",
    "        restricted = set(restricted)\n",
    "        visited = set()\n",
    "        queue = [0]\n",
    "\n",
    "        count = 0\n",
    "        while queue:\n",
    "            node = queue.pop(0)\n",
    "            if node not in visited and node not in restricted:\n",
    "                count += 1\n",
    "                visited.add(node)\n",
    "                for neighbor in graph[node]:\n",
    "                    if neighbor not in visited and neighbor not in restricted:\n",
    "                        queue.append(neighbor)\n",
    "\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        e=collections.defaultdict(list)\n",
    "        restricted=set(restricted)\n",
    "        for a,b in edges:\n",
    "            if b in restricted or a in restricted:\n",
    "                continue\n",
    "            e[a].append(b)  \n",
    "            e[b].append(a)\n",
    "        q=collections.deque()\n",
    "        q.append([0,-1])\n",
    "        ans=0\n",
    "        while q:\n",
    "            tp,pre=q.pop()\n",
    "            #print(tp)\n",
    "            ans+=1\n",
    "            for i in e[tp]:\n",
    "                if i!=pre:\n",
    "                    q.append([i,tp])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        route_map = dict()\n",
    "        for i in range(n):\n",
    "            route_map[i] = []\n",
    "        restricted = set(restricted)\n",
    "        for edge in edges:\n",
    "            if edge[0] in restricted or edge[1] in restricted:\n",
    "                continue\n",
    "            if edge[0] not in route_map[edge[1]]:\n",
    "                route_map[edge[1]].append(edge[0])\n",
    "            if edge[1] not in route_map[edge[0]]:\n",
    "                route_map[edge[0]].append(edge[1])\n",
    "        \n",
    "        result = 1\n",
    "        cur_visit, cur_value = set([0]), set(route_map[0])\n",
    "        while cur_value:\n",
    "            next_value = set()\n",
    "            for value in cur_value:\n",
    "                if value not in cur_visit:\n",
    "                    cur_visit.update([value])\n",
    "                    result += 1\n",
    "                    next_value.update(route_map[value])\n",
    "            cur_value = next_value - cur_visit\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "\t\tif 0 in restricted:\n",
    "\t\t\treturn 0\n",
    "\t\tres = 0\n",
    "\t\tq = collections.deque([0])\n",
    "\t\tgraph = [list() for _ in range(n)]\n",
    "\n",
    "\t\tfor edge in edges: \n",
    "\t\t\tgraph[edge[0]].append(edge[1])\n",
    "\t\t\tgraph[edge[1]].append(edge[0])\n",
    "\n",
    "\t\tvis = set(restricted)\n",
    "\t\tvis.add(0)\n",
    "\n",
    "\t\twhile q:\n",
    "\t\t\troot = q.popleft()\n",
    "\t\t\tvis.add(root)\n",
    "\t\t\tres += 1\n",
    "\t\t\tfor child in graph[root]:\n",
    "\t\t\t\tif child not in vis:\n",
    "\t\t\t\t\tq.append(child)\n",
    "\n",
    "\t\treturn res\t\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        def bfs(node: int) -> int:\n",
    "            ans = 1 # node 0\n",
    "            queue = deque([node])\n",
    "            while queue:\n",
    "                node = queue.popleft()\n",
    "                for neighbor in graph[node]:\n",
    "                    if neighbor not in visited:\n",
    "                        ans += 1\n",
    "                        queue.append(neighbor)\n",
    "                        visited.add(neighbor)\n",
    "\n",
    "            return ans\n",
    "        \n",
    "        # 1. O(E) build adjacency list for tree\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for u,v in edges:\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "        \n",
    "        # 2. BFS O(V) traverse tree\n",
    "        visited = set(restricted)\n",
    "        visited.add(0)\n",
    "        ans = bfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        mp = collections.defaultdict(list)\n",
    "        rst = set(restricted)\n",
    "        for a, b in edges:\n",
    "            mp[a].append(b)\n",
    "            mp[b].append(a)\n",
    "\n",
    "        \n",
    "        queue = collections.deque([0])\n",
    "        seen = set()\n",
    "        seen.add(0)\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            res += 1\n",
    "\n",
    "            for nxt in mp[node]:\n",
    "                if nxt not in seen and nxt not in rst:\n",
    "                    queue.append(nxt)\n",
    "                    seen.add(nxt)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        graph = defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "        seen = set()\n",
    "        restricted = set(restricted)\n",
    "        q = deque([0])\n",
    "        seen.add(0)\n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "            for neighbor in graph[node]:\n",
    "                if neighbor not in seen and neighbor not in restricted:\n",
    "                    q.append(neighbor)\n",
    "                    seen.add(neighbor)\n",
    "        return len(seen)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        graph = defaultdict(list)\n",
    "        for u,v in edges:\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "        \n",
    "        visited = set(restricted)\n",
    "        visited.add(0)\n",
    "        \n",
    "        ans = 1\n",
    "        deque = collections.deque([0])\n",
    "        while deque:    \n",
    "            u = deque.popleft()\n",
    "            for v in graph[u]:\n",
    "                if v not in visited:\n",
    "                    visited.add(v)\n",
    "                    deque.append(v)\n",
    "                    ans += 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        graph = {}\n",
    "        for n1, n2 in edges:\n",
    "            graph[n1] = graph.get(n1, []) + [n2]\n",
    "            graph[n2] = graph.get(n2, []) + [n1]\n",
    "        ans = 1\n",
    "        stack = [0]\n",
    "        visited = set(restricted + [0])\n",
    "        while stack:\n",
    "            root = stack.pop()\n",
    "            children = graph[root]\n",
    "            for child in children:\n",
    "                if child in visited:\n",
    "                    continue\n",
    "                ans +=1\n",
    "                visited.add(child)\n",
    "                stack.append(child)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        #拓扑排序;从0开始,一定可以继续\n",
    "        restricted = set(restricted)\n",
    "        path = defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            path[a] += b,\n",
    "            path[b] += a,   #双向通路\n",
    "        #加一个visit 然后bfs遍历好了\n",
    "        vis = [1] + [0] * n\n",
    "        run = [0]\n",
    "        while run:\n",
    "            t = run.pop()\n",
    "            to = path[t]\n",
    "            for x in to:\n",
    "                if x not in restricted and vis[x] == 0:\n",
    "                    run += x,\n",
    "                    vis[x] = 1\n",
    "        return sum(vis)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        g = {}\n",
    "        for x, y in edges:\n",
    "            if x not in g:\n",
    "                g[x] = set()\n",
    "            if y not in g:\n",
    "                g[y] = set()\n",
    "            \n",
    "            g[x].add(y)\n",
    "            g[y].add(x)\n",
    "        \n",
    "        q = [0]\n",
    "        l = 0\n",
    "        r = 1\n",
    "        used = set(restricted)\n",
    "        used.add(0)\n",
    "        while l < r:\n",
    "            now = q[l]\n",
    "            l += 1\n",
    "            for next in g.get(now, set()):\n",
    "                if next not in used:\n",
    "                    used.add(next)\n",
    "                    q.append(next)\n",
    "                    r += 1\n",
    "        \n",
    "        return len(q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\r\n",
    "\r\n",
    "class UnionFind:\r\n",
    "    def __init__(self, n):\r\n",
    "        self.parent = list(range(n))\r\n",
    "        \r\n",
    "    def find(self, x):\r\n",
    "        if self.parent[x] != x:\r\n",
    "            self.parent[x] = self.find(self.parent[x])\r\n",
    "            \r\n",
    "        return self.parent[x]\r\n",
    "\r\n",
    "    def union(self, x, y):\r\n",
    "        root_x = self.find(x)\r\n",
    "        root_y = self.find(y)\r\n",
    "        \r\n",
    "        if root_x != root_y:\r\n",
    "            self.parent[root_x] = root_y\r\n",
    "        \r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\r\n",
    "        uf = UnionFind(n)\r\n",
    "        ban = set(restricted)\r\n",
    "        for x, y in edges:\r\n",
    "            if x in ban or y in ban:\r\n",
    "                continue\r\n",
    "            uf.union(x, y)\r\n",
    "        \r\n",
    "        \r\n",
    "        \r\n",
    "        return sum([uf.find(0) == uf.find(x) for x in range(n)])\r\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        fa = list(range(n))\n",
    "        def find(x):\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def merge(x, y):\n",
    "            fa[find(x)] = find(y)\n",
    "        r = set(restricted)\n",
    "        for edge in edges:\n",
    "            if edge[0] in r or edge[1] in r:\n",
    "                continue\n",
    "            merge(edge[0], edge[1])\n",
    "        p = find(0)\n",
    "        return sum(1 for i in range(n) if find(i) == p)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        r = set(restricted)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            if x not in r and y not in r:\n",
    "                g[x].append(y)\n",
    "                g[y].append(x)\n",
    "        ans = 0\n",
    "        def dfs(x: int, fa: int) -> None:\n",
    "            nonlocal ans\n",
    "            ans += 1\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    dfs(y, x)\n",
    "        dfs(0, -1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        def dfs(node: int) -> None:\n",
    "            if visited[node]:\n",
    "                return \n",
    "            visited[node] = True \n",
    "            nonlocal ans \n",
    "            ans += 1 \n",
    "            for neighbor in g[node]:\n",
    "                dfs(neighbor)\n",
    "        \n",
    "        # 1. O(E) build adjacency list for tree\n",
    "        # only edge of two unrestricted node can add to graph\n",
    "        restricted = set(restricted)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            if a not in restricted and b not in restricted:\n",
    "                g[a].append(b)\n",
    "                g[b].append(a)\n",
    "        \n",
    "        # 2. O(V) traverse tree\n",
    "        ans = 0\n",
    "        visited = [False] * n \n",
    "        dfs(0)\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        r = set(restricted)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            if x not in r and y not in r:\n",
    "                g[x].append(y)\n",
    "                g[y].append(x)\n",
    "        ans = 0\n",
    "        def dfs(x: int, fa: int) -> None:\n",
    "            nonlocal ans\n",
    "            ans += 1\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    dfs(y, x)\n",
    "        dfs(0, -1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        res = set(restricted)\n",
    "        neighbors = [[] for i in range(n)]\n",
    "        for edge in edges:\n",
    "            if edge[0] in res or edge[1] in res: continue\n",
    "            neighbors[edge[0]].append(edge[1])\n",
    "            neighbors[edge[1]].append(edge[0])\n",
    "        visited = [0] * n \n",
    "        def dfs(i):\n",
    "            if visited[i] > 0: return\n",
    "            visited[i] = 1\n",
    "            for j in neighbors[i]: dfs(j)\n",
    "            return\n",
    "        dfs(0)\n",
    "        ans = 0\n",
    "        for i in visited: ans += i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        r = set(restricted)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            if x not in r and y not in r:\n",
    "                g[x].append(y)\n",
    "                g[y].append(x)\n",
    "        ans = 0\n",
    "        def dfs(x: int, fa: int) -> None:\n",
    "            nonlocal ans\n",
    "            ans += 1\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    dfs(y, x)\n",
    "        dfs(0, -1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        # 哈表记录那些节点是受限的， 建图时，只有当两个节点都不是受限的才连边。然后dfs这棵树，统计从0出发能访问到的节点树，即为答案\n",
    "        # dfs 带限制的dfs节点遍历\n",
    "        r = set(restricted)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            if x not in r and y not in r:\n",
    "                g[x].append(y)\n",
    "                g[y].append(x)\n",
    "\n",
    "        ans = 0\n",
    "        def dfs(x:int, fa:int) -> None:\n",
    "            nonlocal ans\n",
    "            ans += 1\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    dfs(y, x)\n",
    "        dfs(0, -1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        r = set(restricted)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            if x not in r and y not in r:\n",
    "                g[x].append(y)\n",
    "                g[y].append(x)\n",
    "        ans = 0\n",
    "        def dfs(x: int, fa: int) -> None:\n",
    "            nonlocal ans\n",
    "            ans += 1\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    dfs(y, x)\n",
    "        dfs(0, -1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        r = set(restricted)\n",
    "        tree = [[] for _ in range(n)]\n",
    "        for a,b in edges:\n",
    "            if a not in r and b not in r:\n",
    "                tree[a].append(b)\n",
    "                tree[b].append(a)\n",
    "\n",
    "        ans = 0\n",
    "        def dfs(x: int, fa: int) -> None:\n",
    "            nonlocal ans\n",
    "            ans += 1\n",
    "            for y in tree[x]:\n",
    "                if y != fa:\n",
    "                    dfs(y, x)\n",
    "\n",
    "        dfs(0, -1)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        r = set(restricted)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            if x not in r and y not in r:\n",
    "                g[x].append(y)\n",
    "                g[y].append(x)\n",
    "        ans = 0\n",
    "        def dfs(x: int, fa: int) -> None:\n",
    "            nonlocal ans\n",
    "            ans += 1\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    dfs(y, x)\n",
    "        dfs(0, -1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        grid = [[] for _ in range(n)]\n",
    "        restricted = set(restricted)\n",
    "        for a, b in edges:\n",
    "            if a not in restricted and b not in restricted:\n",
    "                grid[a].append(b)\n",
    "                grid[b].append(a)\n",
    "        \n",
    "        self.ans = 0\n",
    "        def dfs(node, last):\n",
    "            self.ans += 1\n",
    "            for n in grid[node]:\n",
    "                if n != last:\n",
    "                    dfs(n, node)\n",
    "        \n",
    "        dfs(0, -1)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        g=[[] for _ in range(n)]\n",
    "        ans=0\n",
    "        r=set(restricted)\n",
    "        for a, b in edges:\n",
    "            if a not in r and b not in r:\n",
    "                g[a].append(b)\n",
    "                g[b].append(a)\n",
    "        def dfs(i,fa):\n",
    "            nonlocal ans\n",
    "            ans+=1\n",
    "            for j in g[i]:\n",
    "                if j != fa:\n",
    "                    dfs(j,i)\n",
    "        dfs(0,-1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        r = set(restricted)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            if x not in r and y not in r:\n",
    "                g[x].append(y)\n",
    "                g[y].append(x)\n",
    "        ans = 0\n",
    "        def dfs(x: int, fa: int) -> None:\n",
    "            nonlocal ans\n",
    "            ans += 1\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    dfs(y, x)\n",
    "        dfs(0, -1)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        r = set(restricted)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            if x not in r and y not in r:\n",
    "                g[x].append(y)\n",
    "                g[y].append(x)\n",
    "        ans = 0\n",
    "        def dfs(x: int, fa: int) -> None:\n",
    "            nonlocal ans\n",
    "            ans += 1\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    dfs(y, x)\n",
    "        dfs(0, -1)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        r = set(restricted)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            if x not in r and y not in r:\n",
    "                g[x].append(y)\n",
    "                g[y].append(x)\n",
    "        ans = 0\n",
    "        def dfs(x: int, fa: int) -> None:\n",
    "            nonlocal ans\n",
    "            ans += 1\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    dfs(y, x)\n",
    "        dfs(0, -1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "#         r = set(restricted)\n",
    "#         tree = [[] for _ in range(n)]\n",
    "#         for a,b in edges:\n",
    "#             if a not in r and b not in r:\n",
    "#                 tree[a].append(b)\n",
    "#                 tree[b].append(a)\n",
    "\n",
    "#         ans = 0\n",
    "#         def dfs(x: int, fa: int) -> None:\n",
    "#             nonlocal ans\n",
    "#             ans += 1\n",
    "#             for y in tree[x]:\n",
    "#                 if y != fa:\n",
    "#                     dfs(y, x)\n",
    "\n",
    "#         dfs(0, -1)\n",
    "\n",
    "#         return ans\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        tree = [[] for _ in range(n)]\n",
    "        for a,b in edges:\n",
    "            tree[a].append(b)\n",
    "            tree[b].append(a)\n",
    "\n",
    "        ans = 0\n",
    "        r = set(restricted)\n",
    "        def dfs(node, father):\n",
    "            if node in r:\n",
    "                return \n",
    "            \n",
    "            nonlocal ans\n",
    "            ans += 1\n",
    "            for x in tree[node]:\n",
    "                if x != father:\n",
    "                    dfs(x, node)\n",
    "\n",
    "        dfs(0, -1)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        limit = set(restricted)\n",
    "        connects = [[] for _ in range(n)]\n",
    "        for (x, y) in edges:\n",
    "            if x not in limit and y not in limit:\n",
    "                connects[x].append(y)\n",
    "                connects[y].append(x)\n",
    "        \n",
    "        res = 0\n",
    "        def dfs(x, pre):\n",
    "            nonlocal res\n",
    "            res += 1\n",
    "            for y in connects[x]:\n",
    "                if y != pre:\n",
    "                    dfs(y, x)\n",
    "        dfs(0, -1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        g = [[] for i in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        r = set(restricted)\n",
    "        res = 0\n",
    "        def dfs(x, p):\n",
    "            if x in r:\n",
    "                return\n",
    "            nonlocal res\n",
    "            res += 1\n",
    "            for y in g[x]:\n",
    "                if y != p:\n",
    "                    dfs(y, x)\n",
    "        dfs(0, -1)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        g=[[] for _ in range(n)]\n",
    "        ans=0\n",
    "        r=set(restricted)\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        def dfs(i,fa):\n",
    "            nonlocal ans\n",
    "            if i in r:\n",
    "                return \n",
    "            ans+=1\n",
    "            for j in g[i]:\n",
    "                if j != fa:\n",
    "                    dfs(j,i)\n",
    "        dfs(0,-1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        ans = 1\n",
    "        r = set(restricted)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            if x not in r and y not in r:\n",
    "                g[x].append(y)\n",
    "                g[y].append(x)\n",
    "        \n",
    "        ans = 0\n",
    "        def dfs(x, fa):\n",
    "            nonlocal ans\n",
    "            ans += 1\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    dfs(y, x)\n",
    "        \n",
    "        dfs(0, -1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        g = [[] for i in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        r = set(restricted)\n",
    "        res = 0\n",
    "        def dfs(x, p):\n",
    "            if x in r:\n",
    "                return\n",
    "            nonlocal res\n",
    "            res += 1\n",
    "            for y in g[x]:\n",
    "                if y != p:\n",
    "                    dfs(y, x)\n",
    "        dfs(0, -1)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        grid = [[] for _ in range(n)]\n",
    "        restricted = set(restricted)\n",
    "        for a, b in edges:\n",
    "            if a not in restricted and b not in restricted:\n",
    "                grid[a].append(b)\n",
    "                grid[b].append(a)\n",
    "        \n",
    "        self.ans = 0\n",
    "        def dfs(node, last):\n",
    "            for n in grid[node]:\n",
    "                if n != last:\n",
    "                    dfs(n, node)\n",
    "            self.ans += 1\n",
    "        \n",
    "        dfs(0, -1)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        restricted = set(restricted)\n",
    "        ans = 0\n",
    "\n",
    "        def dfs(node, fa):\n",
    "            nonlocal ans \n",
    "            if node in restricted:\n",
    "                return \n",
    "            ans += 1\n",
    "            for nxt in g[node]:\n",
    "                if nxt != fa:\n",
    "                    dfs(nxt, node)\n",
    "        \n",
    "        dfs(0, -1)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        grid = [[] for _ in range(n)]\n",
    "        restricted = set(restricted)\n",
    "        for a, b in edges:\n",
    "            if a not in restricted and b not in restricted:\n",
    "                grid[a].append(b)\n",
    "                grid[b].append(a)\n",
    "        \n",
    "        ans = 0\n",
    "        def dfs(node, last):\n",
    "            nonlocal ans\n",
    "            ans += 1\n",
    "            for n in grid[node]:\n",
    "                if n != last:\n",
    "                    dfs(n, node)\n",
    "        \n",
    "        dfs(0, -1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        restricted_set = set(restricted)\n",
    "        for a, b in edges:\n",
    "            if a not in restricted_set and b not in restricted_set:\n",
    "                g[a].append(b)\n",
    "                g[b].append(a)\n",
    "\n",
    "        count = 0\n",
    "        def dfs(node, prenode):\n",
    "            nonlocal count\n",
    "            count += 1\n",
    "            for p in g[node]:\n",
    "                if p == prenode:\n",
    "                    continue\n",
    "                dfs(p, node)\n",
    "        dfs(0, -1)\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        g=[[] for _ in range(n)]\n",
    "        ans=0\n",
    "        r=set(restricted)\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        def dfs(i,fa):\n",
    "            nonlocal ans\n",
    "            if i in r:\n",
    "                return \n",
    "            ans+=1\n",
    "            for j in g[i]:\n",
    "                if j != fa:\n",
    "                    dfs(j,i)\n",
    "        dfs(0,-1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        r=set(restricted)\n",
    "        ans=0\n",
    "        p=[[]for _ in range(n)]\n",
    "        for x,y in edges:\n",
    "            if x not in r and y not in r:\n",
    "                p[x].append(y)\n",
    "                p[y].append(x)\n",
    "        def dfs(x,f):\n",
    "            nonlocal ans\n",
    "            ans+=1\n",
    "            for nxt in p[x]:\n",
    "                if nxt!=f:\n",
    "                    dfs(nxt,x)\n",
    "        dfs(0,-1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        ans=0\n",
    "        d=[[]for i in range(n)]\n",
    "        v=[True for i in range(n)]\n",
    "        for i,j in edges:\n",
    "            d[i].append(j)\n",
    "            d[j].append(i)\n",
    "        for i in restricted:\n",
    "            v[i]=False\n",
    "        v[0]=False\n",
    "        def dfs(x):\n",
    "            nonlocal ans\n",
    "            for i in d[x]:\n",
    "                if v[i]:\n",
    "                    v[i]=False\n",
    "                    dfs(i)\n",
    "                    ans+=1\n",
    "        dfs(0)\n",
    "        return ans+1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for a,b in edges:\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "        book = [0]*n\n",
    "        restricted = set(restricted)\n",
    "        def dfs(i):\n",
    "            res = 1\n",
    "            for j in graph[i]:\n",
    "                if(book[j] == 0 and j not in restricted):\n",
    "                    book[j] = 1\n",
    "                    res += dfs(j)\n",
    "            return res\n",
    "        book[0] = 1\n",
    "        return dfs(0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        restricted = set(restricted)\n",
    "        ans = 0\n",
    "        inAndOut = [[] for _ in range(n)]\n",
    "        visited = [False for _ in range(n)]\n",
    "        for start,end in edges:\n",
    "            inAndOut[start].append(end)\n",
    "            inAndOut[end].append(start)\n",
    "        def dfs(index):\n",
    "            if visited[index] or (index in restricted):\n",
    "                return\n",
    "            nonlocal ans\n",
    "            ans += 1\n",
    "            visited[index] = True\n",
    "            for i in inAndOut[index]:\n",
    "                dfs(i)\n",
    "        dfs(0)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        restricted = set(restricted)\n",
    "        ans = 0\n",
    "        inAndOut = [[] for _ in range(n)]\n",
    "        visited = [False for _ in range(n)]\n",
    "        for start,end in edges:\n",
    "            inAndOut[start].append(end)\n",
    "            inAndOut[end].append(start)\n",
    "        def dfs(index):\n",
    "            if visited[index] or (index in restricted):\n",
    "                return\n",
    "            nonlocal ans\n",
    "            ans += 1\n",
    "            visited[index] = True\n",
    "            for i in inAndOut[index]:\n",
    "                dfs(i)\n",
    "        dfs(0)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        restricted = set(restricted)\n",
    "        ans = 0\n",
    "        inAndOut = [[] for _ in range(n)]\n",
    "        visited = [False for _ in range(n)]\n",
    "        for start,end in edges:\n",
    "            if start not in restricted and end not in restricted:\n",
    "                inAndOut[start].append(end)\n",
    "                inAndOut[end].append(start)\n",
    "        def dfs(index):\n",
    "            if visited[index] or (index in restricted):\n",
    "                return\n",
    "            nonlocal ans\n",
    "            ans += 1\n",
    "            visited[index] = True\n",
    "            for i in inAndOut[index]:\n",
    "                dfs(i)\n",
    "        dfs(0)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for a,b in edges:\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "        book = [0]*n\n",
    "        restricted = set(restricted)\n",
    "        def dfs(i):\n",
    "            res = 1\n",
    "            for j in graph[i]:\n",
    "                if(book[j] == 0 and j not in restricted):\n",
    "                    book[j] = 1\n",
    "                    res += dfs(j)\n",
    "            return res\n",
    "        book[0] = 1\n",
    "        return dfs(0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        ans=0\n",
    "        d=[[]for i in range(n)]\n",
    "        v=[True for i in range(n)]\n",
    "        for i,j in edges:\n",
    "            d[i].append(j)\n",
    "            d[j].append(i)\n",
    "        for i in restricted:\n",
    "            v[i]=False\n",
    "        v[0]=False\n",
    "        def dfs(x):\n",
    "            nonlocal ans\n",
    "            for i in d[x]:\n",
    "                if v[i]:\n",
    "                    v[i]=False\n",
    "                    dfs(i)\n",
    "                    ans+=1\n",
    "        dfs(0)\n",
    "        return ans+1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for a,b in edges:\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "        book = [0]*n\n",
    "        restricted = set(restricted)\n",
    "        def dfs(i):\n",
    "            res = 1\n",
    "            for j in graph[i]:\n",
    "                if(book[j] == 0 and j not in restricted):\n",
    "                    book[j] = 1\n",
    "                    res += dfs(j)\n",
    "            return res\n",
    "        book[0] = 1\n",
    "        return dfs(0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        restricted = set(restricted)\n",
    "        for a,b in edges:\n",
    "            if a in restricted or b in restricted: continue\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        \n",
    "        def f(x,pa):\n",
    "            if x in restricted: return 0\n",
    "            res = 1\n",
    "            for y in g[x]:\n",
    "                if y == pa: continue\n",
    "                res += f(y,x)\n",
    "            return res\n",
    "        \n",
    "        return f(0,-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a,b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        restricted = set(restricted)\n",
    "        \n",
    "        def f(x,pa):\n",
    "            if x in restricted: return 0\n",
    "            res = 1\n",
    "            for y in g[x]:\n",
    "                if y == pa: continue\n",
    "                res += f(y,x)\n",
    "            return res\n",
    "        \n",
    "        return f(0,-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        ret = 0\n",
    "        restricted = set(restricted)\n",
    "        def dfs(node, fa):\n",
    "            nonlocal ret\n",
    "            ret += 1\n",
    "            for son in g[node]:\n",
    "                if son == fa or son in restricted:\n",
    "                    continue\n",
    "                dfs(son, node)\n",
    "        dfs(0, -1)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        g=[[] for i in range(n)]\n",
    "        for edge in edges:\n",
    "            g[edge[0]].append(edge[1])\n",
    "            g[edge[1]].append(edge[0])\n",
    "        sset=set(restricted)\n",
    "        ans=1\n",
    "        def dfs(x, fa):\n",
    "            nonlocal ans\n",
    "            for y in g[x]:\n",
    "                if y==fa:\n",
    "                    continue\n",
    "                if y not in sset:\n",
    "                    ans+=1\n",
    "                    dfs(y, x)\n",
    "        dfs(0,-1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        g = [[] for i in range(n)]\n",
    "        for (u,v) in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "\n",
    "        s = set(restricted)\n",
    "        self.cnt = 0\n",
    "        def dfs(i):\n",
    "            s.add(i)\n",
    "            self.cnt += 1\n",
    "            for j in g[i]:\n",
    "                if j in s: continue\n",
    "                dfs(j)\n",
    "        \n",
    "        dfs(0)\n",
    "        return self.cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        g = [[] for i in range(n)]\n",
    "        for (u,v) in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "\n",
    "        s = set(restricted)\n",
    "        self.cnt = 0\n",
    "        def dfs(i):\n",
    "            if i in s:\n",
    "                return\n",
    "            s.add(i)\n",
    "            self.cnt += 1\n",
    "            for j in g[i]:\n",
    "                dfs(j)\n",
    "        \n",
    "        dfs(0)\n",
    "        return self.cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        restricted_set = {x for x in restricted}\n",
    "        seen = set()\n",
    "        count = 0\n",
    "        def dfs(node):\n",
    "            nonlocal count\n",
    "            if node in seen or node in restricted_set:\n",
    "                return\n",
    "            count += 1\n",
    "            seen.add(node)\n",
    "            for p in g[node]:\n",
    "                dfs(p)\n",
    "        dfs(0)\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        restricted_set = set(restricted)\n",
    "        seen = set()\n",
    "        count = 0\n",
    "        def dfs(node):\n",
    "            nonlocal count\n",
    "            if node in seen or node in restricted_set:\n",
    "                return\n",
    "            count += 1\n",
    "            seen.add(node)\n",
    "            for p in g[node]:\n",
    "                dfs(p)\n",
    "        dfs(0)\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        restricted_set = set(restricted)\n",
    "        for a, b in edges:\n",
    "            if a not in restricted_set and b not in restricted_set:\n",
    "                g[a].append(b)\n",
    "                g[b].append(a)\n",
    "        \n",
    "        seen = set()\n",
    "        count = 0\n",
    "        def dfs(node):\n",
    "            nonlocal count\n",
    "            if node in seen or node in restricted_set:\n",
    "                return\n",
    "            count += 1\n",
    "            seen.add(node)\n",
    "            for p in g[node]:\n",
    "                dfs(p)\n",
    "        dfs(0)\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        vis = set()\n",
    "        limit = set(restricted)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a,b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "\n",
    "        def dfs(x):\n",
    "            for y in g[x]:\n",
    "                if y not in vis and y not in limit:\n",
    "                    vis.add(y)\n",
    "                    dfs(y)\n",
    "            pass\n",
    "        \n",
    "        vis.add(0)\n",
    "        dfs(0)\n",
    "        return len(vis)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:\n",
    "        restricted = set(restricted)\n",
    "        ans = 0\n",
    "        g = defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "\n",
    "        def dfs(u, fa):\n",
    "            nonlocal ans \n",
    "            ans += 1\n",
    "            for v in g[u]:\n",
    "                if v != fa and v not in restricted:\n",
    "                    dfs(v,u)\n",
    "\n",
    "        dfs(0, 0)\n",
    "        return ans "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
